<!DOCTYPE html>



  


<html class="theme-next muse use-motion" lang>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/blog/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/blog/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/blog/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/blog/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/blog/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/blog/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT">





  <link rel="alternate" href="/blog/atom.xml" title="编程那点事" type="application/atom+xml">






<meta property="og:type" content="website">
<meta property="og:title" content="编程那点事">
<meta property="og:url" content="https://lhweb.gitee.io/blog/page/3/index.html">
<meta property="og:site_name" content="编程那点事">
<meta property="og:locale" content="default">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="编程那点事">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Muse',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://lhweb.gitee.io/blog/page/3/">





  <title>编程那点事</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="default">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">编程那点事</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/blog/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/blog/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            Archives
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/24/详解JS中的this、apply、call、bind/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/24/详解JS中的this、apply、call、bind/" itemprop="url">详解JS中的this、apply、call、bind</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-24T09:17:27+08:00">
                2018-09-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/javascript/" itemprop="url" rel="index">
                    <span itemprop="name">javascript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>这又是一个面试经典问题~/(ㄒoㄒ)/~~也是 ES5中众多坑中的一个，在 ES6 中可能会极大避免 this 产生的错误，但是为了一些老代码的维护，最好还是了解一下 this 的指向和 call、apply、bind 三者的区别。</p>
<h1 id="this-的指向"><a href="#this-的指向" class="headerlink" title="this 的指向"></a>this 的指向</h1><p>在 ES5 中，其实 this 的指向，始终坚持一个原理：this 永远指向最后调用它的那个对象，来，跟着我朗读三遍：this 永远指向最后调用它的那个对象，this 永远指向最后调用它的那个对象，this 永远指向最后调用它的那个对象。记住这句话，this 你已经了解一半了。</p>
<p>下面我们来看一个最简单的例子：</p>
<p>例 1：</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">a</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line"> <span class="keyword">var</span> name = <span class="string">"Cherry"</span>;</span><br><span class="line"> <span class="built_in">console</span>.log(<span class="keyword">this</span>.name);   <span class="comment">// windowsName</span></span><br><span class="line"> <span class="built_in">console</span>.log(<span class="string">"inner:"</span> + <span class="keyword">this</span>); <span class="comment">// inner: Window</span></span><br><span class="line">&#125;</span><br><span class="line">a();</span><br><span class="line"><span class="built_in">console</span>.log(<span class="string">"outer:"</span> + <span class="keyword">this</span>)   <span class="comment">// outer: Window</span></span><br></pre></td></tr></table></figure>
<p>这个相信大家都知道为什么 log 的是 windowsName，因为根据刚刚的那句话“this 永远指向最后调用它的那个对象”，我们看最后调用 a 的地方 a();，前面没有调用的对象那么就是全局对象 window，这就相当于是 window.a()；注意，这里我们没有使用严格模式，如果使用严格模式的话，全局对象就是 undefined，那么就会报错 Uncaught TypeError: Cannot read property ‘name’ of undefined。</p>
<p>再看下这个例子：</p>
<p>例 2：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"> <span class="keyword">var</span> a = &#123;</span><br><span class="line">  name: <span class="string">"Cherry"</span>,</span><br><span class="line">  fn : <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   <span class="built_in">console</span>.log(<span class="keyword">this</span>.name);  <span class="comment">// Cherry</span></span><br><span class="line">  &#125;</span><br><span class="line"> &#125;</span><br><span class="line"> a.fn();</span><br></pre></td></tr></table></figure></p>
<p>在这个例子中，函数 fn 是对象 a 调用的，所以打印的值就是 a 中的 name 的值。是不是有一点清晰了呢~</p>
<p>我们做一个小小的改动：</p>
<p>例 3：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"> <span class="keyword">var</span> a = &#123;</span><br><span class="line">  name: <span class="string">"Cherry"</span>,</span><br><span class="line">  fn : <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   <span class="built_in">console</span>.log(<span class="keyword">this</span>.name);  <span class="comment">// Cherry</span></span><br><span class="line">  &#125;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="built_in">window</span>.a.fn();</span><br></pre></td></tr></table></figure></p>
<p>这里打印 Cherry 的原因也是因为刚刚那句话“this 永远指向最后调用它的那个对象”，最后调用它的对象仍然是对象 a。</p>
<p>我们再来看一下这个例子：</p>
<p>例 4：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"><span class="keyword">var</span> a = &#123;</span><br><span class="line"> <span class="comment">// name: "Cherry",</span></span><br><span class="line"> fn : <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="keyword">this</span>.name);  <span class="comment">// undefined</span></span><br><span class="line"> &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="built_in">window</span>.a.fn();</span><br></pre></td></tr></table></figure></p>
<p>这里为什么会打印 undefined 呢？这是因为正如刚刚所描述的那样，调用 fn 的是 a 对象，也就是说 fn 的内部的 this 是对象 a，而对象 a 中并没有对 name 进行定义，所以 log 的 this.name 的值是 undefined。</p>
<p>这个例子还是说明了：this 永远指向最后调用它的那个对象，因为最后调用 fn 的对象是 a，所以就算 a 中没有 name 这个属性，也不会继续向上一个对象寻找 this.name，而是直接输出 undefined。</p>
<p>再来看一个比较坑的例子：</p>
<p>例 5：</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"><span class="keyword">var</span> a = &#123;</span><br><span class="line"> name : <span class="literal">null</span>,</span><br><span class="line"> <span class="comment">// name: "Cherry",</span></span><br><span class="line"> fn : <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="keyword">this</span>.name);  <span class="comment">// windowsName</span></span><br><span class="line"> &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">var</span> f = a.fn;</span><br><span class="line">f();</span><br></pre></td></tr></table></figure>
<p>这里你可能会有疑问，为什么不是 Cherry，这是因为虽然将 a 对象的 fn 方法赋值给变量 f 了，但是没有调用，再接着跟我念这一句话：“this 永远指向最后调用它的那个对象”，由于刚刚的 f 并没有调用，所以 fn() 最后仍然是被 window 调用的。所以 this 指向的也就是 window。</p>
<p>由以上五个例子我们可以看出，this 的指向并不是在创建的时候就可以确定的，在 es5 中，永远是this 永远指向最后调用它的那个对象。</p>
<p>再来看一个例子：</p>
<p>例 6：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">fn</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line"> <span class="keyword">var</span> name = <span class="string">'Cherry'</span>;</span><br><span class="line"> innerFunction();</span><br><span class="line"> <span class="function"><span class="keyword">function</span> <span class="title">innerFunction</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="keyword">this</span>.name);  <span class="comment">// windowsName</span></span><br><span class="line"> &#125;</span><br><span class="line">&#125;</span><br><span class="line">fn()</span><br></pre></td></tr></table></figure></p>
<p>读到现在了应该能够理解这是为什么了吧(oﾟ▽ﾟ)o。</p>
<h1 id="怎么改变-this-的指向"><a href="#怎么改变-this-的指向" class="headerlink" title="怎么改变 this 的指向"></a>怎么改变 this 的指向</h1><p>改变 this 的指向我总结有以下几种方法：</p>
<h2 id="使用-ES6-的箭头函数"><a href="#使用-ES6-的箭头函数" class="headerlink" title="使用 ES6 的箭头函数"></a>使用 ES6 的箭头函数</h2><p>在函数内部使用 _this = this</p>
<h2 id="使用-apply、call、bind"><a href="#使用-apply、call、bind" class="headerlink" title="使用 apply、call、bind"></a>使用 apply、call、bind</h2><p>new 实例化一个对象</p>
<p>例 7：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"> <span class="keyword">var</span> a = &#123;</span><br><span class="line">  name : <span class="string">"Cherry"</span>,</span><br><span class="line">  func1: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   <span class="built_in">console</span>.log(<span class="keyword">this</span>.name)  </span><br><span class="line">  &#125;,</span><br><span class="line">  func2: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   setTimeout( <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.func1()</span><br><span class="line">   &#125;,<span class="number">100</span>);</span><br><span class="line">  &#125;</span><br><span class="line"> &#125;;</span><br><span class="line"> a.func2()  <span class="comment">// this.func1 is not a function</span></span><br></pre></td></tr></table></figure></p>
<p> 在不使用箭头函数的情况下，是会报错的，因为最后调用 setTimeout 的对象是 window，但是在 window 中并没有 func1 函数。</p>
<p>我们在改变 this 指向这一节将把这个例子作为 demo 进行改造。</p>
<h1 id="箭头函数"><a href="#箭头函数" class="headerlink" title="箭头函数"></a>箭头函数</h1><p>众所周知，ES6 的箭头函数是可以避免 ES5 中使用 this 的坑的。箭头函数的 this 始终指向函数定义时的 this，而非执行时。，箭头函数需要记着这句话：“箭头函数中没有 this 绑定，必须通过查找作用域链来决定其值，如果箭头函数被非箭头函数包含，则 this 绑定的是最近一层非箭头函数的 this，否则，this 为 undefined”。</p>
<p>例 8 ：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"><span class="keyword">var</span> a = &#123;</span><br><span class="line"> name : <span class="string">"Cherry"</span>,</span><br><span class="line"> func1: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="keyword">this</span>.name)  </span><br><span class="line"> &#125;,</span><br><span class="line"> func2: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  setTimeout( <span class="function"><span class="params">()</span> =&gt;</span> &#123;</span><br><span class="line">   <span class="keyword">this</span>.func1()</span><br><span class="line">  &#125;,<span class="number">100</span>);</span><br><span class="line"> &#125;</span><br><span class="line">&#125;;</span><br><span class="line">a.func2()  <span class="comment">// Cherry</span></span><br></pre></td></tr></table></figure></p>
<p>在函数内部使用 _this = this</p>
<p>如果不使用 ES6，那么这种方式应该是最简单的不会出错的方式了，我们是先将调用这个函数的对象保存在变量 _this 中，然后在函数中都使用这个 _this，这样 _this 就不会改变了。</p>
<p>例 9：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> name = <span class="string">"windowsName"</span>;</span><br><span class="line"><span class="keyword">var</span> a = &#123;</span><br><span class="line"> name : <span class="string">"Cherry"</span>,</span><br><span class="line"> func1: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="keyword">this</span>.name)  </span><br><span class="line"> &#125;,</span><br><span class="line"> func2: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">var</span> _this = <span class="keyword">this</span>;</span><br><span class="line">  setTimeout( <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">   _this.func1()</span><br><span class="line">  &#125;,<span class="number">100</span>);</span><br><span class="line"> &#125;</span><br><span class="line">&#125;;</span><br><span class="line">a.func2()  <span class="comment">// Cherry</span></span><br></pre></td></tr></table></figure></p>
<p>这个例子中，在 func2 中，首先设置 var _this = this;，这里的 this 是调用 func2 的对象 a，为了防止在 func2 中的 setTimeout 被 window 调用而导致的在 setTimeout 中的 this 为 window。我们将 this(指向变量 a) 赋值给一个变量 _this，这样，在 func2 中我们使用 _this 就是指向对象 a 了。</p>
<h1 id="使用-apply、call、bind-1"><a href="#使用-apply、call、bind-1" class="headerlink" title="使用 apply、call、bind"></a>使用 apply、call、bind</h1><p>使用 apply、call、bind 函数也是可以改变 this 的指向的，原理稍后再讲，我们先来看一下是怎么实现的：</p>
<h2 id="使用-apply"><a href="#使用-apply" class="headerlink" title="使用 apply"></a>使用 apply</h2><p>例 10：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> a = &#123;</span><br><span class="line"> name : <span class="string">"Cherry"</span>,</span><br><span class="line"> func1: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="keyword">this</span>.name)</span><br><span class="line"> &#125;,</span><br><span class="line"> func2: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  setTimeout( <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   <span class="keyword">this</span>.func1()</span><br><span class="line">  &#125;.apply(a),<span class="number">100</span>);</span><br><span class="line"> &#125;</span><br><span class="line">&#125;;</span><br><span class="line">a.func2()   <span class="comment">// Cherry</span></span><br></pre></td></tr></table></figure></p>
<h2 id="使用-call"><a href="#使用-call" class="headerlink" title="使用 call"></a>使用 call</h2><p>例 11：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> a = &#123;</span><br><span class="line"> name : <span class="string">"Cherry"</span>,</span><br><span class="line"> func1: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(<span class="keyword">this</span>.name)</span><br><span class="line"> &#125;,</span><br><span class="line"> func2: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">  setTimeout( <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   <span class="keyword">this</span>.func1()</span><br><span class="line">  &#125;.call(a),<span class="number">100</span>);</span><br><span class="line"> &#125;</span><br><span class="line">&#125;;</span><br><span class="line">a.func2()   <span class="comment">// Cherry</span></span><br></pre></td></tr></table></figure></p>
<h2 id="使用-bind"><a href="#使用-bind" class="headerlink" title="使用 bind"></a>使用 bind</h2><p>例 12：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> a = &#123;</span><br><span class="line">  name : <span class="string">"Cherry"</span>,</span><br><span class="line">  func1: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   <span class="built_in">console</span>.log(<span class="keyword">this</span>.name)</span><br><span class="line">  &#125;,</span><br><span class="line">  func2: <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">   setTimeout( <span class="function"><span class="keyword">function</span> (<span class="params"></span>) </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.func1()</span><br><span class="line">   &#125;.bind(a)(),<span class="number">100</span>);</span><br><span class="line">  &#125;</span><br><span class="line"> &#125;;</span><br><span class="line"> a.func2()   <span class="comment">// Cherry</span></span><br></pre></td></tr></table></figure></p>
<h1 id="apply、call、bind-区别"><a href="#apply、call、bind-区别" class="headerlink" title="apply、call、bind 区别"></a>apply、call、bind 区别</h1><p>刚刚我们已经介绍了 apply、call、bind 都是可以改变 this 的指向的，但是这三个函数稍有不同。</p>
<p>在 MDN 中定义 apply 如下；</p>
<p>apply() 方法调用一个函数, 其具有一个指定的this值，以及作为一个数组（或类似数组的对象）提供的参数</p>
<h2 id="apply-的语法为："><a href="#apply-的语法为：" class="headerlink" title="apply 的语法为："></a>apply 的语法为：</h2><p><code>fun.apply(thisArg, [argsArray])</code><br>thisArg：在 fun 函数运行时指定的 this 值。需要注意的是，指定的 this 值并不一定是该函数执行时真正的 this 值，如果这个函数处于非严格模式下，则指定为 null 或 undefined 时会自动指向全局对象（浏览器中就是window对象），同时值为原始值（数字，字符串，布尔值）的 this 会指向该原始值的自动包装对象。</p>
<p>argsArray：一个数组或者类数组对象，其中的数组元素将作为单独的参数传给 fun 函数。如果该参数的值为null 或 undefined，则表示不需要传入任何参数。从ECMAScript 5 开始可以使用类数组对象。浏览器兼容性请参阅本文底部内容。<br>apply 和 call 的区别</p>
<p>其实 apply 和 call 基本类似，他们的区别只是传入的参数不同。</p>
<h2 id="call-的语法为："><a href="#call-的语法为：" class="headerlink" title="call 的语法为："></a>call 的语法为：</h2><p><code>fun.call(thisArg[, arg1[, arg2[, ...]]])</code></p>
<p>所以 apply 和 call 的区别是 call 方法接受的是若干个参数列表，而 apply 接收的是一个包含多个参数的数组。</p>
<p>例 13：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> a =&#123;</span><br><span class="line">  name : <span class="string">"Cherry"</span>,</span><br><span class="line">  fn : <span class="function"><span class="keyword">function</span> (<span class="params">a,b</span>) </span>&#123;</span><br><span class="line">   <span class="built_in">console</span>.log( a + b)</span><br><span class="line">  &#125;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="keyword">var</span> b = a.fn;</span><br><span class="line"> b.apply(a,[<span class="number">1</span>,<span class="number">2</span>])  <span class="comment">// 3</span></span><br></pre></td></tr></table></figure></p>
<p>例 14：<br> <figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> a =&#123;</span><br><span class="line"> name : <span class="string">"Cherry"</span>,</span><br><span class="line"> fn : <span class="function"><span class="keyword">function</span> (<span class="params">a,b</span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log( a + b)</span><br><span class="line"> &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">var</span> b = a.fn;</span><br><span class="line">b.call(a,<span class="number">1</span>,<span class="number">2</span>)  <span class="comment">// 3</span></span><br></pre></td></tr></table></figure></p>
<p> bind 和 apply、call 区别</p>
<p>我们先来将刚刚的例子使用 bind 试一下<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> a =&#123;</span><br><span class="line"> name : <span class="string">"Cherry"</span>,</span><br><span class="line"> fn : <span class="function"><span class="keyword">function</span> (<span class="params">a,b</span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log( a + b)</span><br><span class="line"> &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">var</span> b = a.fn;</span><br><span class="line">b.bind(a,<span class="number">1</span>,<span class="number">2</span>)</span><br></pre></td></tr></table></figure></p>
<p>我们会发现并没有输出，这是为什么呢，我们来看一下 MDN 上的文档说明：</p>
<p>bind()方法创建一个新的函数, 当被调用时，将其this关键字设置为提供的值，在调用新函数时，在任何提供之前提供一个给定的参数序列。<br>所以我们可以看出，bind 是创建一个新的函数，我们必须要手动去调用：<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> a =&#123;</span><br><span class="line">  name : <span class="string">"Cherry"</span>,</span><br><span class="line">  fn : <span class="function"><span class="keyword">function</span> (<span class="params">a,b</span>) </span>&#123;</span><br><span class="line">   <span class="built_in">console</span>.log( a + b)</span><br><span class="line">  &#125;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="keyword">var</span> b = a.fn;</span><br><span class="line"> b.bind(a,<span class="number">1</span>,<span class="number">2</span>)()   <span class="comment">// 3</span></span><br></pre></td></tr></table></figure></p>
<h1 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h1><p>以上所述是小编给大家介绍的JS中的this、apply、call、bind，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持！</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/前端性能优化常用技术手段-JavaScript-面向切面编程-AOP-入门/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/前端性能优化常用技术手段-JavaScript-面向切面编程-AOP-入门/" itemprop="url">前端性能优化常用技术手段--JavaScript 面向切面编程(AOP)入门</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T22:12:58+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/javascript/" itemprop="url" rel="index">
                    <span itemprop="name">javascript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h1 id="面向切面编程的概念解读"><a href="#面向切面编程的概念解读" class="headerlink" title="面向切面编程的概念解读"></a>面向切面编程的概念解读</h1><h2 id="什么是面向切面编程？"><a href="#什么是面向切面编程？" class="headerlink" title="什么是面向切面编程？"></a>什么是面向切面编程？</h2><blockquote>
<p>Aspect Oriented Programming (AOP)，面向切面编程，是一个比较热门的话题。AOP主要实现的目的是针对业务处理过程中的切面进行提取，它所面对的是处理过程中的某个步骤或阶段，以获得逻辑过程中各部分之间低耦合性的隔离效果。– 面向切面编程_百度百科</p>
</blockquote>
<h2 id="用普通的大白话去解释上面比较官方的话"><a href="#用普通的大白话去解释上面比较官方的话" class="headerlink" title="用普通的大白话去解释上面比较官方的话"></a>用普通的大白话去解释上面比较官方的话</h2><ul>
<li><p>什么是切面</p>
<blockquote>
<p>比如说我们用刀切一块面包，那么切过之后在我们眼前的这个面就是所谓的切面</p>
</blockquote>
</li>
<li><p>面向切面比较热门是因为它有很多的优点，因为它可以进行那种无侵入的干扰</p>
<blockquote>
<p>比如说还是我们有一块面包，切得时候不乱切，从他的开头或者结尾的地方进行切取，而不是从中间横切竖切，如果我们按照这种顺序来切就始终能保留着它有一块完整的面包，如果说乱切又横切又竖切这样的话这块面包就乱掉了，所以面向切面编程最大的优点就是它可以对业务进行无侵入的干扰</p>
</blockquote>
</li>
<li><p>“AOP 主要的目的是针对业务处理过程中的切面进行提取”</p>
<blockquote>
<p>这句话就是说：你想要吃面包就从两头切就好了，而不要从中间乱动</p>
</blockquote>
</li>
<li><p>“它所面对的是处理过程中的某个步骤或阶段”</p>
<blockquote>
<p>这句话是说：他所面对的肯定是我们当前需要处理的业务中的某个部分， 要对这个业务进行一系列的操作，以及对这个业务进行相应的提取和隔离，我们不对人家具体的业务进行干扰，我们只对这个业务进行操作，将这个业务放到开头或者结尾表面的位置</p>
</blockquote>
</li>
<li><p>“以获得逻辑过程中各部分之间低耦合性的隔离效果”</p>
<blockquote>
<p>这句话是说：如果你往人家的业务里面穿插了一些代码，比如说比较常用的例子：要做一个网页的性能检测，那么就要在我们的 html 代码里面穿插各种各样比较讨厌的节点，然后再加很多东西，或者说你用 js 来做，在 js 中埋下 N 多的埋点，然后再恰当的时机再 send 给服务器，如果说你把这个做成面向切面的话，就是不在里面进行埋点，而是在整体的业务逻辑上给它加对应的东西，然后这个东西在需要执行的函数之前或者之后执行，这样的话如果有一天进行了热插拔，将真正的函数给抽走了，那么这样对原来人家的逻辑也不会有任何的影响，那么你这个埋点的工作就和人家原来的执行函数没有任何相应的混淆，他也能进行这种隔离效果</p>
</blockquote>
</li>
</ul>
<h2 id="用图片来解释上面的逻辑"><a href="#用图片来解释上面的逻辑" class="headerlink" title="用图片来解释上面的逻辑"></a>用图片来解释上面的逻辑</h2><p><img src="/blog/2018/09/23/前端性能优化常用技术手段-JavaScript-面向切面编程-AOP-入门/前端性能优化常用技术手段-TypeScript-面向切面编程-AOP-入门/timg.jpg" alt="image.png"></p>
<blockquote>
<p>上图的是一个地板，这个地板对向我们的这个面就是我们用刀把地板横割出来的一个面，那么如果说我们想测这个地板的高度和宽度的话，我们是不需要在它的里面打一个一个的小点然后一点点的那么去测的，我们最常用的方法肯定是：上下表面在上表面用米尺往下一钩、压紧了，然后一看显示的就是这个的高了，同样的道理在横向的方向这样一压尺子也就能知道这个的宽了，这个就是通过他的上下面、左右面就能拿到对应的想要拿到的数据了，这个例子就是所谓的面向切面编程了</p>
</blockquote>
<h1 id="JavaScript-面向切面编程的代码实战"><a href="#JavaScript-面向切面编程的代码实战" class="headerlink" title="JavaScript 面向切面编程的代码实战"></a>JavaScript 面向切面编程的代码实战</h1><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">test</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">    alert(<span class="number">2</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="string">'me test'</span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="built_in">Function</span>.prototype.before = <span class="function"><span class="keyword">function</span>(<span class="params">fn</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">var</span> __self = <span class="keyword">this</span>;</span><br><span class="line">   </span><br><span class="line">   <span class="keyword">return</span> <span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">       <span class="keyword">if</span>(fn.apply(<span class="keyword">this</span>,<span class="built_in">arguments</span>) == <span class="literal">false</span>)&#123; </span><br><span class="line">           <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">       &#125;</span><br><span class="line"></span><br><span class="line">       <span class="keyword">return</span> __self.apply(__self, <span class="built_in">arguments</span>); </span><br><span class="line">      &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">Function</span>.prototype.after = <span class="function"><span class="keyword">function</span>(<span class="params">fn</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">var</span> __self = <span class="keyword">this</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">        <span class="keyword">var</span> result = __self.apply(__self,<span class="built_in">arguments</span>);</span><br><span class="line">        <span class="keyword">if</span>(result == <span class="literal">false</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        fn.apply(<span class="keyword">this</span>,<span class="built_in">arguments</span>);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">test.after(<span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">    alert(<span class="number">3</span>);</span><br><span class="line">&#125;).before(<span class="function"><span class="keyword">function</span>(<span class="params"></span>)</span>&#123;</span><br><span class="line">    alert(<span class="number">1</span>);</span><br><span class="line">&#125;)();</span><br></pre></td></tr></table></figure>
<h1 id="要理解AOP编程就必须理解apply"><a href="#要理解AOP编程就必须理解apply" class="headerlink" title="要理解AOP编程就必须理解apply"></a>要理解AOP编程就必须理解apply</h1><p>总结一句话：apply() 就是用来让括号里的对象 来集成括号外的函数的属性！可以称之为继承！</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/TypeScript设计模式之策略、模板方法/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/TypeScript设计模式之策略、模板方法/" itemprop="url">TypeScript设计模式之策略、模板方法</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T21:49:54+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/typescript/" itemprop="url" rel="index">
                    <span itemprop="name">typescript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>看看用TypeScript怎样实现常见的设计模式，顺便复习一下。<br>学模式最重要的不是记UML，而是知道什么模式可以解决什么样的问题，在做项目时碰到问题可以想到用哪个模式可以解决，UML忘了可以查，思想记住就好。<br>这里尽量用原创的，实际中能碰到的例子来说明模式的特点和用处。</p>
<h1 id="策略模式-Strategy"><a href="#策略模式-Strategy" class="headerlink" title="策略模式 Strategy"></a>策略模式 Strategy</h1><p>特点：用组合的方式调用一些算法或逻辑，并且可以根据状态不同而选用不同的算法或逻辑。<br>用处：对象需要运行时切换算法或逻辑可以考虑使用策略模式。<br>注意：策略的生成方式。<br>下面用TypeScript简单实现一个策略模式：<br>说起策略就想到策略类游戏，年龄大点的可能都玩过War3，人族对兽族时如果侦察到对方不着急升本，用常规万金油打法，那人族就可以出狗男女来一波流。<br>如果侦察到兽族跳科技并摆下两个兽栏，那对方可能是暴飞龙，人族就要家里补个塔防偷农民，然后出点火枪或二本龙鹰。<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Orc</span></span>&#123;</span><br><span class="line">    private _shenKeJi = <span class="literal">false</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">get</span> shenKeJi(): boolean &#123; <span class="comment">// 这里简单用升科技来判断是用常规还是飞龙</span></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">this</span>._shenKeJi;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">set</span> shenKeJi(value: boolean)&#123;</span><br><span class="line">        <span class="keyword">this</span>._shenKeJi = value;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">abstract <span class="class"><span class="keyword">class</span> <span class="title">Stragety</span></span>&#123;</span><br><span class="line">    abstract execute();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">RushStragety</span> <span class="keyword">extends</span> <span class="title">Stragety</span></span>&#123;</span><br><span class="line">    execute()&#123;</span><br><span class="line">        <span class="built_in">console</span>.log(<span class="string">'升科技'</span>);</span><br><span class="line">        <span class="built_in">console</span>.log(<span class="string">'出狗男女'</span>);</span><br><span class="line">        <span class="built_in">console</span>.log(<span class="string">'一波流'</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">DefendStragety</span> <span class="keyword">extends</span> <span class="title">Stragety</span></span>&#123;</span><br><span class="line">    execute()&#123;</span><br><span class="line">        <span class="built_in">console</span>.log(<span class="string">'补塔防飞龙'</span>);</span><br><span class="line">        <span class="built_in">console</span>.log(<span class="string">'出火枪'</span>);</span><br><span class="line">        <span class="built_in">console</span>.log(<span class="string">'升科技'</span>);</span><br><span class="line">        <span class="built_in">console</span>.log(<span class="string">'出龙鹰'</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Human</span></span>&#123;</span><br><span class="line">    stragety: Stragety;</span><br><span class="line"></span><br><span class="line">    checkOrc(orc: Orc)&#123;</span><br><span class="line">        <span class="keyword">if</span>(orc.shenKeJi)&#123; <span class="comment">//根据兽族情况来决定策略</span></span><br><span class="line">            <span class="built_in">console</span>.log(<span class="string">'侦察到兽族是跳科技打法'</span>);</span><br><span class="line">            <span class="keyword">this</span>.stragety = <span class="keyword">new</span> DefendStragety();</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="built_in">console</span>.log(<span class="string">'侦察到兽族是常规打法'</span>);</span><br><span class="line">            <span class="keyword">this</span>.stragety = <span class="keyword">new</span> RushStragety();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    deal()&#123;</span><br><span class="line">        <span class="keyword">this</span>.stragety &amp;&amp; <span class="keyword">this</span>.stragety.execute();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> orc = <span class="keyword">new</span> Orc();</span><br><span class="line"><span class="keyword">let</span> human = <span class="keyword">new</span> Human();</span><br><span class="line"></span><br><span class="line">orc.shenKeJi = <span class="literal">false</span>;</span><br><span class="line">human.checkOrc(orc);</span><br><span class="line">human.deal();</span><br><span class="line"></span><br><span class="line">orc.shenKeJi = <span class="literal">true</span>;</span><br><span class="line">human.checkOrc(orc);</span><br><span class="line">human.deal();</span><br><span class="line"></span><br><span class="line"><span class="comment">//输出</span></span><br><span class="line">侦察到兽族是常规打法</span><br><span class="line">升科技</span><br><span class="line">出狗男女</span><br><span class="line">一波流</span><br><span class="line"></span><br><span class="line">侦察到兽族是跳科技打法</span><br><span class="line">补塔防飞龙</span><br><span class="line">出火枪</span><br><span class="line">升科技</span><br><span class="line">出龙鹰</span><br></pre></td></tr></table></figure></p>
<p>这样人族就可以根据兽族的状态改变来做出不同的应对策略，其实现在游戏的AI基本都是通过决策树来实现的，也算是策略模式，只是更复杂，通过各种不同的条件最终得到一个决策来做出反应。</p>
<p>另外，有人可能已经发现了，上面生成策略的地方是可以拿出来，用之前讲的工厂模式来做，因为实际应用时策略通常比较多，甚至可能同时需要多种相关策略，用工厂模式来生产策略就可以很好的隐藏细节，解除依赖。</p>
<h1 id="模板方法模式-Template-Method"><a href="#模板方法模式-Template-Method" class="headerlink" title="模板方法模式 Template Method"></a>模板方法模式 Template Method</h1><p>特点：通过多态来实现在运行时使用不同的算法或逻辑，通常有一个整体架子，通过抽象方法或虚方法来把细节代码延迟到子类实现。<br>用处：当多个类似功能的类有很多相同结构或代码时，可以抽象出整体架子时可以考虑模板方法。<br>注意：与策略模式的异同：同样是细节部分交出去，不同在于策略是对象行为，采用的是组合的方式，而模板方法是类行为，采用的是继承。<br>下面用TypeScript简单实现一个模板方法模式：<br>比方说发送http请求的代码，需要向两台不同的server(A和B)发送请求，两台server除了url不同，回来的数据格式也不一样，但由于都是http请求，主体架子是一样的，所以可以用模板方法来实现下。<br><figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">ClassA</span></span>&#123;&#125; <span class="comment">// Server A 返回的数据结构</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">ClassB</span></span>&#123;&#125; <span class="comment">// Server B 返回的数据结构</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">abstract</span> <span class="class"><span class="keyword">class</span> <span class="title">RequesterBase&lt;T&gt;</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    constructor(<span class="keyword">private</span> url: string)&#123;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    reqeustData(): <span class="type">T</span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.sendReqeust();</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">this</span>.handleResponse();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">protected</span> sendReqeust()&#123;</span><br><span class="line">        console.log(`send request, url: $&#123;<span class="keyword">this</span>.url&#125;`);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">protected</span> <span class="keyword">abstract</span> handleResponse(): <span class="type">T</span>; <span class="comment">// 不同的server返回的数据交由子类去实现</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">RequesterForServerA</span> <span class="keyword">extends</span> <span class="title">RequesterBase&lt;ClassA&gt;</span></span>&#123;</span><br><span class="line">    <span class="keyword">protected</span> handleResponse(): <span class="type">ClassA</span>&#123;</span><br><span class="line">        console.log(<span class="symbol">'handle</span> response <span class="keyword">for</span> <span class="type">Server</span> <span class="type">A</span>');</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">RequesterForServerB</span> <span class="keyword">extends</span> <span class="title">RequesterBase&lt;ClassB&gt;</span></span>&#123;</span><br><span class="line">    <span class="keyword">protected</span> handleResponse(): <span class="type">ClassB</span>&#123;</span><br><span class="line">        console.log(<span class="symbol">'handle</span> response <span class="keyword">for</span> <span class="type">Server</span> <span class="type">B</span>');</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">let requesterA: <span class="type">RequesterBase</span>&lt;<span class="type">ClassA</span>&gt; = <span class="keyword">new</span> <span class="type">RequesterForServerA</span>(<span class="symbol">'server</span> <span class="type">A</span>');</span><br><span class="line">let requesterB: <span class="type">RequesterBase</span>&lt;<span class="type">ClassB</span>&gt; = <span class="keyword">new</span> <span class="type">RequesterForServerB</span>(<span class="symbol">'server</span> <span class="type">B</span>');</span><br><span class="line"></span><br><span class="line">requesterA.reqeustData();</span><br><span class="line">requesterB.reqeustData();</span><br><span class="line"></span><br><span class="line"><span class="comment">//输出</span></span><br><span class="line">send request, url: server <span class="type">A</span></span><br><span class="line">handle response <span class="keyword">for</span> <span class="type">Server</span> <span class="type">A</span></span><br><span class="line"></span><br><span class="line">send request, url: server <span class="type">B</span></span><br><span class="line">handle response <span class="keyword">for</span> <span class="type">Server</span> <span class="type">B</span></span><br></pre></td></tr></table></figure></p>
<p>这里可以看到主体功能由基类RequesterBase实现，两个子类则实现解析数据这些细节，这样就达到了消除重复代码的目的。<br>如果还有个ServerC的request发送部分也不一样，也没关系，TypeScript天生虚函数，在子类直接实现reqeustData即可，多态的作用下，运行时还是会调用到子类上。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/TypeScript-学习笔记-之-枚举与类型推断/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/TypeScript-学习笔记-之-枚举与类型推断/" itemprop="url">TypeScript 学习笔记 之 枚举与类型推断</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T21:28:57+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/typescript/" itemprop="url" rel="index">
                    <span itemprop="name">typescript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h1 id="枚举"><a href="#枚举" class="headerlink" title="枚举"></a>枚举</h1><ol>
<li><p>默认枚举属性的值为整型,且从0开始自动递增, 如下：</p>
<figure class="highlight crystal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">enum</span> <span class="title">Direction</span>&#123;</span></span><br><span class="line">  Up,Down,Left,Right,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p>也可以指定值。如指定 Up = 1 ，以便枚举从1 开始。</p>
</li>
<li><p>也枚举值也支持字符串类型:</p>
<figure class="highlight crystal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">enum</span> <span class="title">Direction</span>&#123;</span></span><br><span class="line"> Up = <span class="string">"UP"</span>,Down = <span class="string">"DOWN"</span>,Left=<span class="string">"LEFT"</span>,Right=<span class="string">"RIGHT"</span>,</span><br></pre></td></tr></table></figure>
</li>
<li><p>由于 JS 类型的灵活性也支持混合类型的枚举成员，但是一定不推荐这样做。</p>
</li>
<li><p>枚举不仅支持常量值也支持编译期可计算的值。<br>如:</p>
</li>
</ol>
<ul>
<li>引用了其他的枚举常量。</li>
<li>括号内的枚举常量表达式。</li>
<li>使用了 +,-,~ 一元操作符的枚举常量值。</li>
<li>使用了 +,-,*,/,%,&lt;&lt;,&gt;&gt;,&amp;,|,^ 二元操作符的枚举常量表达 式。</li>
</ul>
<ol start="6">
<li><p>某些枚举成员也可以当类型使用，示例如下：</p>
<figure class="highlight routeros"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">enum ShapeKind&#123;</span><br><span class="line">  Circle,</span><br><span class="line">  Square,</span><br><span class="line">&#125;</span><br><span class="line">interface Circle&#123;</span><br><span class="line">  kind: ShapeKind.Circle;</span><br><span class="line">  radius:number;</span><br><span class="line">&#125;</span><br><span class="line">interface Square&#123;</span><br><span class="line">  kind: ShapeKind.Square;</span><br><span class="line">  sideLength: number;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p>枚举成员也可以当对象使用，因为它在运行期的确是有对应存在的。</p>
</li>
<li><p>对于数值类型的枚举，以枚举成员作为属性访问枚举类可以获得对应的枚举成员的属性名。</p>
</li>
<li><p>const 枚举。声明为 const 的枚举只存在于编译期，生成的代码中将删除。</p>
</li>
<li><p>Ambient 枚举。用于描述在其他地方已经存在的枚举类型。</p>
<figure class="highlight crystal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">declare <span class="class"><span class="keyword">enum</span> <span class="title">Enum</span>&#123;</span></span><br><span class="line">  A = <span class="number">1</span>,</span><br><span class="line">  B,</span><br><span class="line">  C = <span class="number">2</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ol>
<h1 id="类型推断"><a href="#类型推断" class="headerlink" title="类型推断"></a>类型推断</h1><ol>
<li><p>基本推断 let x = 3; 意味着 let x:number = 3;</p>
</li>
<li><p>最佳公共类型推断对于字面量包含多个值时（比如数组），自动推断的类型有可能是他们的共同的父类型，或者一个联合类型。</p>
</li>
<li><p>上下文类型，例如下面的代码，可以推断出 moveEvent 没有 button 属性。</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">window</span>.onmousedown = <span class="function"><span class="keyword">function</span>(<span class="params">mouseEvent</span>)</span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(mouseEvent.button); <span class="comment">// &lt;- Error</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ol>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/学习JavaScript数据结构与算法（四）：二叉搜索树/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/学习JavaScript数据结构与算法（四）：二叉搜索树/" itemprop="url">学习JavaScript数据结构与算法（四）：二叉搜索树</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T20:15:13+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/javascript/" itemprop="url" rel="index">
                    <span itemprop="name">javascript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <blockquote>
<p><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%80%EF%BC%89%EF%BC%9A%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/">学习JavaScript数据结构与算法（一）：栈与队列</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%BA%8C%EF%BC%89%EF%BC%9A%E9%93%BE%E8%A1%A8/">学习JavaScript数据结构与算法（二）：链表</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%89%EF%BC%89%EF%BC%9A%E9%9B%86%E5%90%88/">学习JavaScript数据结构与算法（三）：集合</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E5%9B%9B%EF%BC%89%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/">学习JavaScript数据结构与算法（四）：二叉搜索树</a></p>
</blockquote>
<h1 id="我与二叉树的前尘往事"><a href="#我与二叉树的前尘往事" class="headerlink" title="我与二叉树的前尘往事"></a>我与二叉树的前尘往事</h1><p>在刚学编程时，就知道有一种数据结构叫“树”，树中的翘楚是“二叉树”，“红黑树”等。<br>据说“树”构在编程界呼风唤雨无所不能。让无数程序员闻风丧胆。甚至在面试时，更是有“手写二叉树”，“翻转二叉树”等题目坐镇。</p>
<p>好吧，我承认这些在当时都把我吓住了。</p>
<p>但是当我颤抖着打开《学习JavaScript数据结构与算法》，开始敲下关于“树”的代码时，突然觉得，好像也没有那么难呢。<br>于是心怀激动，一口气敲完了书上的例子，中途也思考了很久，不断的在纸上演算等。但总的来说，还是学的很开心的。</p>
<h1 id="树の简介"><a href="#树の简介" class="headerlink" title="树の简介"></a>树の简介</h1><p>之前学的栈、队列、链表等数据结构，都是顺序数据结构。而树，将会是我们学的第一种非顺序数据结构。</p>
<p>放在现实里呢，有个很生动的例子，公司组织架构图。长这样:<br><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（四）：二叉搜索树/tree1.png" alt="公司组织架构图"></p>
<p>而我们要学的树，长这样:<br><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（四）：二叉搜索树/tree.png" alt="树の图示"></p>
<h2 id="节点简介"><a href="#节点简介" class="headerlink" title="节点简介"></a>节点简介</h2><p>其中，树中的每个元素，都叫做节点。从节点延伸而下的，叫子节点。<br>树顶部的节点叫根节点。每棵树只有一个根节点。（图中15就是根节点）<br>在节点中，有子节点的节点也称为内部节点，没有的话则被称为外部节点或者叶节点。<br>同时在节点中是有祖先和后代关系的，比如节点9的祖先就有13,7,6,15四个。</p>
<h2 id="节点属性"><a href="#节点属性" class="headerlink" title="节点属性"></a>节点属性</h2><p>深度: 节点的深度取决于其祖先的数量，节点9的深度就是4。<br>树的高度，树的高度体现为节点深度的最大值。<br>比如上图，节点深度最大值为4，则树的高度为4。</p>
<h2 id="二叉树与二叉搜索树"><a href="#二叉树与二叉搜索树" class="headerlink" title="二叉树与二叉搜索树"></a>二叉树与二叉搜索树</h2><p>二叉树的最大特点就在于，它的节点最多只有两个子节点:左侧子节点和右侧子节点。<br>二叉搜索树则是二叉树的一种，但它只允许你在左侧节点储存比父节点小的值，右侧只允许储存比父节点大的值。<br>像刚才的这幅图，就是二叉搜索树。<br><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（四）：二叉搜索树/tree2.png" alt="二叉搜索树"><br>而我们本文要学习的内容，就是如何写一个二叉搜索树。</p>
<h2 id="JavaScipt中二叉搜索树的实现"><a href="#JavaScipt中二叉搜索树的实现" class="headerlink" title="JavaScipt中二叉搜索树的实现"></a>JavaScipt中二叉搜索树的实现</h2><p>首先，创建一个构造函数。<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 二叉搜索树的构造函数</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">BinarySearchTree</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="comment">/**</span></span><br><span class="line"><span class="comment">   * 二叉搜索树键的构造函数</span></span><br><span class="line"><span class="comment">   * @param &#123;Number&#125; key 要生成的键值</span></span><br><span class="line"><span class="comment">   */</span></span><br><span class="line">  <span class="keyword">var</span> Node = <span class="function"><span class="keyword">function</span><span class="params">(key)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 键值</span></span><br><span class="line">    <span class="keyword">this</span>.key = key;</span><br><span class="line">    <span class="comment">// 左子节点</span></span><br><span class="line">    <span class="keyword">this</span>.left = <span class="literal">null</span>;</span><br><span class="line">    <span class="comment">// 右子节点</span></span><br><span class="line">    <span class="keyword">this</span>.right = <span class="literal">null</span>;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="comment">/**</span></span><br><span class="line"><span class="comment">   * 二叉树的根节点，不存在时表示为Null</span></span><br><span class="line"><span class="comment">   * @type &#123;Null or Number&#125;</span></span><br><span class="line"><span class="comment">   */</span></span><br><span class="line">  <span class="keyword">var</span> root = <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>在之前提到过的双向链表中，每个节点包含两个指针，一个指向左侧节点，一个指向右侧节点。在二叉搜索树中，每个节点也有两个指针，一个指向左侧子节点，一个指向右侧子节点。但在二叉搜索树中，我们把节点成为键，这是术语。</p>
<p>二叉搜索树需要有如下的方法:</p>
<ul>
<li><p>insert(key): 向树中插入一个新的键</p>
</li>
<li><p>inOrderTraverse(): 通过中序遍历方式，遍历所有节点</p>
</li>
<li><p>preOrderTranverse(): 通过先序遍历方式，遍历所有节点</p>
</li>
<li><p>postOrderTranverse(): 通过后序遍历方式，遍历所有节点</p>
</li>
<li><p>min(): 返回树中最小的值</p>
</li>
<li><p>max(): 返回树中最大的值</p>
</li>
<li><p>search(key): 搜索某个值，在树中则返回true</p>
</li>
<li><p>remove(key): 从树中移除某个键</p>
</li>
</ul>
<p>二叉搜索树的实现，基本都与递归有关（对我来说递归很绕，花了很久才理解）。如果不清楚递归相关概念，可以看看下面的参考链接。</p>
<p><a href="https://www.zhihu.com/question/20507130" target="_blank" rel="noopener">什么是递归</a></p>
<h3 id="insert方法"><a href="#insert方法" class="headerlink" title="insert方法:"></a>insert方法:</h3><p>说明:向树中插入一个新的键<br>实现:<br><figure class="highlight haxe"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 插入某个键到二叉树中</span></span><br><span class="line"><span class="comment"> * @param  &#123;Number&#125; key 要插入的键值</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="built_in">this</span>.insert = <span class="function"><span class="keyword">function</span></span>(key) &#123;</span><br><span class="line">  <span class="comment">// 用传入的值生成二叉树的键</span></span><br><span class="line">  <span class="keyword">var</span> <span class="keyword">new</span><span class="type">Node</span> = <span class="keyword">new</span> <span class="type">Node</span>(key);</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 根节点为Null时，传入的键则为根节点</span></span><br><span class="line">  <span class="comment">// 否则调用insertNode函数来插入子节点</span></span><br><span class="line">  <span class="keyword">if</span> (root === <span class="literal">null</span>) &#123;</span><br><span class="line">    root = <span class="keyword">new</span><span class="type">Node</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    insertNode(root, <span class="keyword">new</span><span class="type">Node</span>)</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 用于插入子节点。</span></span><br><span class="line"><span class="comment"> * @param  &#123;Node&#125; node    根节点</span></span><br><span class="line"><span class="comment"> * @param  &#123;Node&#125; newNode 要插入的节点</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> insertNode = <span class="function"><span class="keyword">function</span></span>(node, <span class="keyword">new</span><span class="type">Node</span>) &#123;</span><br><span class="line">  <span class="comment">//由于二叉搜索树的性质，所以当键值小于当前所在节点的键值</span></span><br><span class="line">  <span class="comment">//则使得左子结点成为新的要比较的节点，进行递归调用</span></span><br><span class="line">  <span class="comment">//如果左子结点为null，则将键值赋值给左子结点。</span></span><br><span class="line">  <span class="comment">//如果键值大于当前所在节点的键值，原理同上。</span></span><br><span class="line">  <span class="keyword">if</span> (<span class="keyword">new</span><span class="type">Node</span>.key &lt; node.key) &#123;</span><br><span class="line">    <span class="keyword">if</span> (node.left === <span class="literal">null</span>) &#123;</span><br><span class="line">      node.left = <span class="keyword">new</span><span class="type">Node</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      insertNode(node.left, <span class="keyword">new</span><span class="type">Node</span>)</span><br><span class="line">    &#125;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (node.right === <span class="literal">null</span>) &#123;</span><br><span class="line">      node.right = <span class="keyword">new</span><span class="type">Node</span></span><br><span class="line"><span class="type"></span>    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      insertNode(node.right, <span class="keyword">new</span><span class="type">Node</span>)</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="inOrderTraverse方法"><a href="#inOrderTraverse方法" class="headerlink" title="inOrderTraverse方法:"></a>inOrderTraverse方法:</h3><p>说明:通过中序遍历方式，遍历所有节点<br>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 中序遍历操作，常用于排序。会把树中元素从小到大的打印出来。</span><br><span class="line"> * 因为在javascript的递归中，遇到递归是，会优先调用递归的函数。直到递归不再进行。</span><br><span class="line"> * 然后会在递归调用的最后一个函数中执行其它语句。再一层层的升上去。</span><br><span class="line"> * 所以中序遍历会有从小到大的输出结果。</span><br><span class="line"> * 后续的先序和后续遍历和这个原理差不多，取决于callback放在哪儿。</span><br><span class="line"> * </span><br><span class="line"> * @param  &#123;Function&#125; callback 获取到节点后的回调函数</span><br><span class="line"> */</span><br><span class="line">this.inOrderTraverse = function(callback) &#123;</span><br><span class="line">  inOrderTraverseNode(root, callback);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * 中序遍历的辅助函数，用于遍历节点</span><br><span class="line"> * @param  &#123;<span class="keyword">Node</span><span class="title">&#125;   node</span>     遍历开始的节点，默认为root</span><br><span class="line"> * @param  &#123;Function&#125; callback 获取到节点后的回调函数</span><br><span class="line"> * @return &#123;[<span class="keyword">type</span>]&#125;            [description]</span><br><span class="line"> */</span><br><span class="line">var inOrderTraverseNode = function(<span class="keyword">node</span><span class="title">, callback</span>) &#123;</span><br><span class="line">  // 当前节点不为NULL则继续递归调用</span><br><span class="line">  if (<span class="keyword">node</span> <span class="title">!= null</span>) &#123;</span><br><span class="line">    inOrderTraverseNode(<span class="keyword">node</span>.<span class="title">left</span>, callback);</span><br><span class="line">    // 获取到节点后，调用的函数</span><br><span class="line">    callback(<span class="keyword">node</span>.<span class="title">key</span>);</span><br><span class="line">    inOrderTraverseNode(<span class="keyword">node</span>.<span class="title">right</span>, callback);</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<p>假如我们这儿加入打印节点值的函数:<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> printNode = <span class="function"><span class="keyword">function</span>(<span class="params">value</span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(value);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">inOrderTraverse(printNode) <span class="comment">// 输出排序后树的值</span></span><br></pre></td></tr></table></figure></p>
<h3 id="preOrderTranverse方法"><a href="#preOrderTranverse方法" class="headerlink" title="preOrderTranverse方法:"></a>preOrderTranverse方法:</h3><p>说明:通过先序遍历方式，遍历所有节点<br>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 前序遍历操作，常用于打印一个结构化的文档</span><br><span class="line"> * @param  &#123;Function&#125; callback 获取到节点后的回调函数</span><br><span class="line"> */</span><br><span class="line">this.preOrderTranverse = function(callback) &#123;</span><br><span class="line">  preOrderTranverseNode(root, callback);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * 前序遍历的辅助函数，用于遍历节点</span><br><span class="line"> * @param  &#123;<span class="keyword">Node</span><span class="title">&#125;   node</span>     遍历开始的节点，默认为root</span><br><span class="line"> * @param  &#123;Function&#125; callback 获取到节点后的回调函数</span><br><span class="line"> */</span><br><span class="line">var preOrderTranverseNode = function(<span class="keyword">node</span><span class="title">, callback</span>) &#123;</span><br><span class="line">  if (<span class="keyword">node</span> <span class="title">!= null</span>) &#123;</span><br><span class="line">    callback(<span class="keyword">node</span>.<span class="title">key</span>);</span><br><span class="line">    preOrderTranverseNode(<span class="keyword">node</span>.<span class="title">left</span>, callback);</span><br><span class="line">    preOrderTranverseNode(<span class="keyword">node</span>.<span class="title">right</span>, callback);</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="postOrderTranverse方法"><a href="#postOrderTranverse方法" class="headerlink" title="postOrderTranverse方法:"></a>postOrderTranverse方法:</h3><p>说明:通过后序遍历方式，遍历所有节点<br>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 后序遍历操作，常用于计算所占空间</span><br><span class="line"> * @param  &#123;Function&#125; callback 获取到节点后的回调函数</span><br><span class="line"> */</span><br><span class="line">this.postOrderTranverse = function(callback) &#123;</span><br><span class="line">  postOrderTranverseNode(root, callback);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * 后序遍历的辅助函数，用于遍历节点</span><br><span class="line"> * @param  &#123;<span class="keyword">Node</span><span class="title">&#125;   node</span>     遍历开始的节点，默认为root</span><br><span class="line"> * @param  &#123;Function&#125; callback 获取到节点后的回调函数</span><br><span class="line"> */</span><br><span class="line">var postOrderTranverseNode = function(<span class="keyword">node</span><span class="title">, callback</span>) &#123;</span><br><span class="line">  postOrderTranverseNode(<span class="keyword">node</span>.<span class="title">left</span>, callback);</span><br><span class="line">  postOrderTranverseNode(<span class="keyword">node</span>.<span class="title">right</span>, callback);</span><br><span class="line">  callback(<span class="keyword">node</span>.<span class="title">key</span>);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="min方法"><a href="#min方法" class="headerlink" title="min方法:"></a>min方法:</h3><p>说明:返回树中最小的值，由二叉搜索树的性质易知，最左侧的为最小值。则只需取得最左侧的值即可。<br>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 返回树中最小的值</span><br><span class="line"> * @return &#123;Function&#125; min函数的辅助函数</span><br><span class="line"> */</span><br><span class="line">this.min = function() &#123;</span><br><span class="line">  return minNode(root);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * min函数的辅助函数</span><br><span class="line"> * @param  &#123;<span class="keyword">Node</span><span class="title">&#125; node</span> 查找开始的节点，默认为root</span><br><span class="line"> */</span><br><span class="line">var minNode = function(<span class="keyword">node</span><span class="title">) &#123;</span></span><br><span class="line"><span class="title">  // 如果node</span>存在，则开始搜索。能避免树的根节点为Null的情况</span><br><span class="line">  if (<span class="keyword">node</span><span class="title">) &#123;</span></span><br><span class="line"><span class="title">    // 只要树的左侧子节点不为null</span>，则把左子节点赋值给当前节点。</span><br><span class="line">    // 若左子节点为null，则该节点肯定为最小值。</span><br><span class="line">    while (<span class="keyword">node</span> <span class="title">&amp;&amp; node</span>.left !== null) &#123;</span><br><span class="line">      <span class="keyword">node</span> <span class="title">= node</span>.left;</span><br><span class="line">    &#125;</span><br><span class="line">    return <span class="keyword">node</span>.<span class="title">key</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  return null;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="max方法"><a href="#max方法" class="headerlink" title="max方法:"></a>max方法:</h3><p>说明:返回树中最大的值，由min函数易知，最大值在最右侧。<br>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 返回树中最大的值</span><br><span class="line"> * @return &#123;Function&#125; max函数的辅助函数</span><br><span class="line"> */</span><br><span class="line">this.max = function() &#123;</span><br><span class="line">  return maxNode(root);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * max函数的辅助函数</span><br><span class="line"> * @param  &#123;<span class="keyword">Node</span><span class="title">&#125; node</span> 查找开始的节点，默认为root</span><br><span class="line"> * @return &#123;Key&#125;      节点的值</span><br><span class="line"> */</span><br><span class="line">var maxNode = function(<span class="keyword">node</span><span class="title">) &#123;</span></span><br><span class="line"><span class="title">  if</span> (<span class="keyword">node</span><span class="title">) &#123;</span></span><br><span class="line"><span class="title">    while</span> (<span class="keyword">node</span> <span class="title">&amp;&amp; node</span>.right !== null) &#123;</span><br><span class="line">      <span class="keyword">node</span> <span class="title">= node</span>.right;</span><br><span class="line">    &#125;</span><br><span class="line">    return <span class="keyword">node</span>.<span class="title">key</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  return null;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="search方法"><a href="#search方法" class="headerlink" title="search方法:"></a>search方法:</h3><p>说明: 搜索某个值，在树中则返回true<br>实现:<br><figure class="highlight xquery"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 搜索某个值是否存在于树中</span><br><span class="line"> * @param  &#123;Node&#125;<span class="built_in"> key</span> 搜索开始的节点，默认<span class="built_in">为root</span></span><br><span class="line"> * @<span class="keyword">return</span> &#123;Function&#125;     search函数的辅助函数</span><br><span class="line"> */</span><br><span class="line">this.search = <span class="keyword">function</span><span class="built_in">(key</span>) &#123;</span><br><span class="line">  <span class="keyword">return</span> searchNode<span class="built_in">(root</span>,<span class="built_in"> key</span>);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * search函数的辅助函数</span><br><span class="line"> * @param  &#123;Node&#125; <span class="type">node</span> 搜索开始的节点，默认<span class="built_in">为root</span></span><br><span class="line"> * @param  &#123;Key&#125;<span class="built_in"> key</span>  要搜索的键值</span><br><span class="line"> * @<span class="keyword">return</span> &#123;Boolean&#125;      找到节点则返<span class="built_in">回true</span>，否则返<span class="built_in">回false</span></span><br><span class="line"> */</span><br><span class="line">var searchNode = <span class="keyword">function</span>(<span class="type">node</span>,<span class="built_in"> key</span>) &#123;</span><br><span class="line">  // 如果根节点不存在，则直接返回null</span><br><span class="line">  <span class="keyword">if</span> (<span class="type">node</span> === null) &#123;</span><br><span class="line">    <span class="keyword">return</span><span class="built_in"> false</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> <span class="keyword">if</span> <span class="built_in">(key</span> &lt; <span class="type">node</span><span class="built_in">.key</span>) &#123;</span><br><span class="line">    searchNode(<span class="type">node</span>.left,<span class="built_in"> key</span>)</span><br><span class="line">  &#125; <span class="keyword">else</span> <span class="keyword">if</span> <span class="built_in">(key</span> &gt; <span class="type">node</span><span class="built_in">.key</span>) &#123;</span><br><span class="line">    searchNode(<span class="type">node</span>.right,<span class="built_in"> key</span>)</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    // 如果该节点值等于传入的值，返<span class="built_in">回true</span></span><br><span class="line">    <span class="keyword">return</span><span class="built_in"> true</span>;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="remove方法"><a href="#remove方法" class="headerlink" title="remove方法:"></a>remove方法:</h3><p>说明:从树中移除某个键，要应对的场景:</p>
<p>只是一个叶节点</p>
<p>有一个子节点</p>
<p>有两个子节点的节点<br>因为要应付不同的场景，所以这是最麻烦的方法了。让我思考了好久才理解。如果你觉得看不懂的话，可以下载源代码把这一段写一遍。</p>
<p>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 从树中移除某个键</span><br><span class="line"> * @param  &#123;Key&#125; key 要移除的键值</span><br><span class="line"> * @return &#123;Function&#125;     remove函数的辅助函数</span><br><span class="line"> */</span><br><span class="line">this.remove = function(key) &#123;</span><br><span class="line">  root = removeNode(root, key);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">/**</span><br><span class="line"> * remove函数的辅助函数</span><br><span class="line"> * @param  &#123;<span class="keyword">Node</span><span class="title">&#125; node</span> 搜索开始的节点，默认为root</span><br><span class="line"> * @param  &#123;Key&#125; key   要移除的键值</span><br><span class="line"> * @return &#123;Boolean&#125;   移除成功则返回<span class="literal">true</span>，否则返回<span class="literal">false</span></span><br><span class="line"> */</span><br><span class="line">var removeNode = function(<span class="keyword">node</span><span class="title">, key</span>) &#123;</span><br><span class="line">  // 如果根节点不存在，则直接返回null</span><br><span class="line">  if (<span class="keyword">node</span> <span class="title">=== root</span>) &#123;</span><br><span class="line">    return null;</span><br><span class="line">  &#125;</span><br><span class="line">  // 未找到节点前，继续递归调用。</span><br><span class="line">  if (key <span class="tag">&lt; node.key) &#123;</span></span><br><span class="line"><span class="tag">    node.left = removeNode(node.left, key)</span></span><br><span class="line"><span class="tag">    return node;</span></span><br><span class="line"><span class="tag">  &#125; else if (key &gt;</span> <span class="keyword">node</span>.<span class="title">key</span>) &#123;</span><br><span class="line">    <span class="keyword">node</span>.<span class="title">right</span> = removeNode(<span class="keyword">node</span>.<span class="title">right</span>, key)</span><br><span class="line">    return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">  &#125; else</span> &#123;</span><br><span class="line">    // 第一种场景：只是一个叶节点</span><br><span class="line">    // 这种情况只需要直接把节点赋值为null即可</span><br><span class="line">    if (<span class="keyword">node</span>.<span class="title">left</span> === null &amp;&amp; <span class="keyword">node</span>.<span class="title">right</span> === null) &#123;</span><br><span class="line">      <span class="keyword">node</span> <span class="title">= null</span>;</span><br><span class="line">      // 处理完直接return节点</span><br><span class="line">      return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">    &#125;</span></span><br><span class="line"><span class="title">    // 第二种场景：有一个子节点</span></span><br><span class="line"><span class="title">    // 如果左节点为null</span>，则代表右节点存在。</span><br><span class="line">    // 于是把当前节点赋值为存在的那个子节点</span><br><span class="line">    if (<span class="keyword">node</span>.<span class="title">left</span> === null) &#123;</span><br><span class="line">      <span class="keyword">node</span> <span class="title">= node</span>.right;</span><br><span class="line">      // 处理完直接return节点</span><br><span class="line">      return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">    &#125; else</span> if (<span class="keyword">node</span>.<span class="title">right</span> == null) &#123;</span><br><span class="line">      <span class="keyword">node</span> <span class="title">= node</span>.left;</span><br><span class="line">      // 处理完直接return节点</span><br><span class="line">      return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">    &#125;</span></span><br><span class="line"><span class="title">    // 第三种场景：有两个子节点</span></span><br><span class="line"><span class="title">    // 首先加入辅助节点，同时找寻右子节点中的最小节点</span></span><br><span class="line"><span class="title">    // 并把当前节点替换为右子节点中的最小节点</span></span><br><span class="line"><span class="title">    // 同时为了避免节点重复，移除右子节点中的最小节点</span></span><br><span class="line"><span class="title">    var</span> aux = findMinNode(<span class="keyword">node</span>.<span class="title">right</span>);</span><br><span class="line">    <span class="keyword">node</span>.<span class="title">key</span> = aux.key;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">node</span>.<span class="title">right</span> = removeNode(<span class="keyword">node</span>.<span class="title">right</span>, aux.key);</span><br><span class="line">    // 处理完直接return节点</span><br><span class="line">    return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">  &#125;</span></span><br><span class="line"><span class="title">&#125;;</span></span><br><span class="line"><span class="title"></span></span><br><span class="line"><span class="title">/**</span></span><br><span class="line"><span class="title"> * remove</span>函数的辅助函数</span><br><span class="line"> * @param  &#123;<span class="keyword">Node</span><span class="title">&#125; node</span> 查找开始的节点，默认为root</span><br><span class="line"> * @return &#123;<span class="keyword">Node</span><span class="title">&#125;      最小的节点</span></span><br><span class="line"><span class="title"> */</span></span><br><span class="line"><span class="title">var</span> findMinNode = function(<span class="keyword">node</span><span class="title">) &#123;</span></span><br><span class="line"><span class="title">  // 如果node</span>存在，则开始搜索。能避免树的根节点为Null的情况</span><br><span class="line">  if (<span class="keyword">node</span><span class="title">) &#123;</span></span><br><span class="line"><span class="title">    // 只要树的左侧子节点不为null</span>，则把左子节点赋值给当前节点。</span><br><span class="line">    // 若左子节点为null，则该节点肯定为最小值。</span><br><span class="line">    while (<span class="keyword">node</span> <span class="title">&amp;&amp; node</span>.left !== null) &#123;</span><br><span class="line">      <span class="keyword">node</span> <span class="title">= node</span>.left;</span><br><span class="line">    &#125;</span><br><span class="line">    return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">  &#125;</span></span><br><span class="line"><span class="title">  return</span> null;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/学习JavaScript数据结构与算法（三）：集合/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/学习JavaScript数据结构与算法（三）：集合/" itemprop="url">学习JavaScript数据结构与算法（三）：集合</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T19:54:50+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/javascript/" itemprop="url" rel="index">
                    <span itemprop="name">javascript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <blockquote>
<p><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%80%EF%BC%89%EF%BC%9A%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/">学习JavaScript数据结构与算法（一）：栈与队列</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%BA%8C%EF%BC%89%EF%BC%9A%E9%93%BE%E8%A1%A8/">学习JavaScript数据结构与算法（二）：链表</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%89%EF%BC%89%EF%BC%9A%E9%9B%86%E5%90%88/">学习JavaScript数据结构与算法（三）：集合</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E5%9B%9B%EF%BC%89%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/">学习JavaScript数据结构与算法（四）：二叉搜索树</a></p>
</blockquote>
<h1 id="集合-Set"><a href="#集合-Set" class="headerlink" title="集合(Set)"></a>集合(Set)</h1><p>说起集合，就想起刚进高中时，数学第一课讲的就是集合。因此在学习集合这种数据结构时，倍感亲切。<br>集合的基本性质有一条: 集合中元素是不重复的。因为这种性质，所以我们选用了对象来作为集合的容器，而非数组。<br>虽然数组也能做到所有不重复，但终究过于繁琐，不如集合。</p>
<h2 id="集合的操作"><a href="#集合的操作" class="headerlink" title="集合的操作"></a>集合的操作</h2><p>集合的基本操作有交集、并集、差集等。这儿我们介绍JavaScipt集合中交集、并集、差集的实现。至于这三个的具体概念，可以看图:<br><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（三）：集合/set.png" alt="交集、并集、差集"></p>
<h2 id="JavaScipt中集合的实现"><a href="#JavaScipt中集合的实现" class="headerlink" title="JavaScipt中集合的实现"></a>JavaScipt中集合的实现</h2><p>首先，创建一个构造函数。<br><figure class="highlight php"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 集合的构造函数</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">Set</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="comment">/**</span></span><br><span class="line"><span class="comment">   * 集合元素的容器，以对象来表示</span></span><br><span class="line"><span class="comment">   * <span class="doctag">@type</span> &#123;Object&#125;</span></span><br><span class="line"><span class="comment">   */</span></span><br><span class="line">  <span class="keyword">var</span> items = &#123;&#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>集合需要有如下方法:</p>
<ul>
<li><p>has(value): 检测集合内是否有某个元素</p>
</li>
<li><p>add(value): 给集合内添加某个元素</p>
</li>
<li><p>remove(value): 移除集合中某个元素</p>
</li>
<li><p>clear(value): 清空集合</p>
</li>
<li><p>size(): 返回集合长度</p>
</li>
<li><p>values(): 返回集合转换的数组</p>
</li>
<li><p>union(otherSet): 返回两个集合的并集</p>
</li>
<li><p>intersection(otherSet): 返回两个集合的交集</p>
</li>
<li><p>difference(otherSet): 返回两个集合的差集</p>
</li>
<li><p>subset(otherSet): 判断该集合是否为传入集合的子集</p>
</li>
</ul>
<h3 id="has方法"><a href="#has方法" class="headerlink" title="has方法:"></a>has方法:</h3><p>说明:集合中元素是不重复的。所以在其它任何操作前，必须用has方法确认集合是否有某个元素。这儿使用了hasOwnProperty方法来检测。<br>实现:<br><figure class="highlight php"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 检测集合内是否有某个元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  &#123;Any&#125;  value    要检测的元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> &#123;Boolean&#125;       如果有，返回true</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">this.has = <span class="function"><span class="keyword">function</span><span class="params">(value)</span> </span>&#123;</span><br><span class="line">  <span class="comment">// hasOwnProperty的问题在于</span></span><br><span class="line">  <span class="comment">// 它是一个方法，所以可能会被覆写</span></span><br><span class="line">  <span class="keyword">return</span> items.hasOwnProperty(value)</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="add方法"><a href="#add方法" class="headerlink" title="add方法:"></a>add方法:</h3><p>说明: 给集合内添加某个元素。<br>实现:<br><figure class="highlight cs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 给集合内添加某个元素</span></span><br><span class="line"><span class="comment"> * @param &#123;Any&#125; value 要被添加的元素</span></span><br><span class="line"><span class="comment"> * @return &#123;Boolean&#125;       添加成功返回True。</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.<span class="keyword">add</span> = function(<span class="keyword">value</span>) &#123;</span><br><span class="line">  <span class="comment">//先检测元素是否存在。</span></span><br><span class="line">  <span class="keyword">if</span> (!<span class="keyword">this</span>.has(<span class="keyword">value</span>)) &#123;</span><br><span class="line">    items[<span class="keyword">value</span>] = <span class="keyword">value</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">//如果元素已存在则返回false</span></span><br><span class="line">  <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="remove方法"><a href="#remove方法" class="headerlink" title="remove方法:"></a>remove方法:</h3><p>说明: 移除集合中某个元素<br>实现:<br><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 移除集合中某个元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  &#123;Any&#125; value 要移除的元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> &#123;Boolean&#125;       移除成功返回True。</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.remove = function(value) &#123;</span><br><span class="line">  <span class="comment">//先检测元素是否存在。</span></span><br><span class="line">  <span class="keyword">if</span> (<span class="keyword">this</span>.has(value)) &#123;</span><br><span class="line">    delete items[value];</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">//如果元素不存在，则删除失败返回false</span></span><br><span class="line">  <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="clear方法"><a href="#clear方法" class="headerlink" title="clear方法:"></a>clear方法:</h3><p>说明: 清空集合<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 清空集合</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.clear = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">this</span>.items = &#123;&#125;;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="size方法"><a href="#size方法" class="headerlink" title="size方法"></a>size方法</h3><p>说明: 返回集合长度，这儿有两种方法。第一种方法使用了Object.keys这个Api，但只支持IE9及以上。第二种则适用于所有浏览器。<br>实现:<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回集合长度，只可用于IE9及以上</span></span><br><span class="line"><span class="comment"> * @return &#123;Number&#125; 集合长度</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.size = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="comment">// Object.keys方法能将对象转化为数组</span></span><br><span class="line">  <span class="comment">// 只可用于IE9及以上，但很方便</span></span><br><span class="line">  <span class="keyword">return</span> <span class="built_in">Object</span>.keys(items).length;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回集合长度，可用于所有浏览器</span></span><br><span class="line"><span class="comment"> * @return &#123;Number&#125; 集合长度</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.sizeLegacy = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">var</span> count = <span class="number">0</span>;</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">var</span> prop <span class="keyword">in</span> items) &#123;</span><br><span class="line">    <span class="keyword">if</span> (items.hasOwnProperty(prop)) &#123;</span><br><span class="line">      ++count;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> count;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="values方法"><a href="#values方法" class="headerlink" title="values方法"></a>values方法</h3><p>说明: 返回集合转换的数组，这儿也有两种方法。理由同上。使用了Object.keys，只能支持IE9及以上。<br>实现:<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回集合转换的数组，只可用于IE9及以上</span></span><br><span class="line"><span class="comment"> * @return &#123;Array&#125; 转换后的数组</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.values = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> <span class="built_in">Object</span>.keys(items);</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回集合转换的数组，可用于所有浏览器</span></span><br><span class="line"><span class="comment"> * @return &#123;Array&#125; 转换后的数组</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.valuesLegacy = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">var</span> keys = [];</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">var</span> key <span class="keyword">in</span> items) &#123;</span><br><span class="line">    keys.push(key)</span><br><span class="line">  &#125;;</span><br><span class="line">  <span class="keyword">return</span> keys;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="union方法"><a href="#union方法" class="headerlink" title="union方法"></a>union方法</h3><p>说明: 返回两个集合的并集<br>实现:<br><figure class="highlight maxima"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回两个集合的并集</span></span><br><span class="line"><span class="comment"> * @param  &#123;Set&#125; otherSet 要进行并集操作的集合</span></span><br><span class="line"><span class="comment"> * @return &#123;Set&#125;          两个集合的并集</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">this.<span class="built_in">union</span> = function(otherSet) &#123;</span><br><span class="line">  //初始化一个新集合，用于表示并集。</span><br><span class="line">  <span class="built_in">var</span> unionSet = <span class="built_in">new</span> Set();</span><br><span class="line">  //将当前集合转换为数组，并依次添加进unionSet</span><br><span class="line">  <span class="built_in">var</span> <span class="built_in">values</span> = this.<span class="built_in">values</span>();</span><br><span class="line">  <span class="keyword">for</span> (<span class="built_in">var</span> i = <span class="number">0</span>; i &lt; <span class="built_in">values</span>.<span class="built_in">length</span>; i++) &#123;</span><br><span class="line">    unionSet.add(<span class="built_in">values</span>[i]);</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  //将其它集合转换为数组，依次添加进unionSet。</span><br><span class="line">  //循环中的add方法保证了不会有重复元素的出现</span><br><span class="line">  <span class="built_in">values</span> = otherSet.<span class="built_in">values</span>();</span><br><span class="line">  <span class="keyword">for</span> (<span class="built_in">var</span> i = <span class="number">0</span>; i &lt; <span class="built_in">values</span>.<span class="built_in">length</span>; i++) &#123;</span><br><span class="line">    unionSet.add(<span class="built_in">values</span>[i]);</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="built_in">return</span> unionSet;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="intersection方法"><a href="#intersection方法" class="headerlink" title="intersection方法"></a>intersection方法</h3><p>说明: 返回两个集合的交集<br>实现:<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回两个集合的交集</span></span><br><span class="line"><span class="comment"> * @param  &#123;Set&#125; otherSet 要进行交集操作的集合</span></span><br><span class="line"><span class="comment"> * @return &#123;Set&#125;          两个集合的交集</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.intersection = <span class="function"><span class="keyword">function</span>(<span class="params">otherSet</span>) </span>&#123;</span><br><span class="line">  <span class="comment">//初始化一个新集合，用于表示交集。</span></span><br><span class="line">  <span class="keyword">var</span> interSectionSet = <span class="keyword">new</span> <span class="built_in">Set</span>();</span><br><span class="line">  <span class="comment">//将当前集合转换为数组</span></span><br><span class="line">  <span class="keyword">var</span> values = <span class="keyword">this</span>.values();</span><br><span class="line">  <span class="comment">//遍历数组，如果另外一个集合也有该元素，则interSectionSet加入该元素。</span></span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; values.length; i++) &#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (otherSet.has(values[i])) &#123;</span><br><span class="line">      interSectionSet.add(values[i])</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> interSectionSet;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="difference方法"><a href="#difference方法" class="headerlink" title="difference方法"></a>difference方法</h3><p>说明: 返回两个集合的差集<br>实现:<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回两个集合的差集</span></span><br><span class="line"><span class="comment"> * @param  &#123;Set&#125; otherSet 要进行差集操作的集合</span></span><br><span class="line"><span class="comment"> * @return &#123;Set&#125;          两个集合的差集</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.difference = <span class="function"><span class="keyword">function</span>(<span class="params">otherSet</span>) </span>&#123;</span><br><span class="line">  <span class="comment">//初始化一个新集合，用于表示差集。</span></span><br><span class="line">  <span class="keyword">var</span> differenceSet = <span class="keyword">new</span> <span class="built_in">Set</span>();</span><br><span class="line">  <span class="comment">//将当前集合转换为数组</span></span><br><span class="line">  <span class="keyword">var</span> values = <span class="keyword">this</span>.values();</span><br><span class="line">  <span class="comment">//遍历数组，如果另外一个集合没有该元素，则differenceSet加入该元素。</span></span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; values.length; i++) &#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (!otherSet.has(values[i])) &#123;</span><br><span class="line">      differenceSet.add(values[i])</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> differenceSet;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="subset方法"><a href="#subset方法" class="headerlink" title="subset方法"></a>subset方法</h3><p>说明: 判断该集合是否为传入集合的子集。这段代码在我自己写完后与书上一比对，觉得自己超级low。我写的要遍历数组三次，书上的只需要一次，算法复杂度远远低于我的。<br>实现:<br><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 判断该集合是否为传入集合的子集</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  &#123;Set&#125; otherSet 传入的集合</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> &#123;Boolean&#125;      是则返回True</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.subset = function(otherSet) &#123;</span><br><span class="line">  <span class="comment">// 第一个判定,如果该集合长度大于otherSet的长度</span></span><br><span class="line">  <span class="comment">// 则直接返回false</span></span><br><span class="line">  <span class="keyword">if</span> (<span class="keyword">this</span>.size() &gt; otherSet.size()) &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="comment">// 将当前集合转换为数组</span></span><br><span class="line">    <span class="keyword">var</span> values = <span class="keyword">this</span>.values();</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; values.length; i++) &#123;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">if</span> (!otherSet.has(values[i])) &#123;</span><br><span class="line">        <span class="comment">// 第二个判定。只要有一个元素不在otherSet中</span></span><br><span class="line">        <span class="comment">// 那么则可以直接判定不是子集，返回false</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h1 id="ES6中的集合"><a href="#ES6中的集合" class="headerlink" title="ES6中的集合"></a>ES6中的集合</h1><p>ES6也提供了集合，但之前看ES6的集合操作一直迷迷糊糊的。实现一遍后再去看，感觉概念清晰了很多。<br>具体的我掌握的不是很好，还在学习中，就不写出来啦~推荐看阮一峰老师的《ECMAScript 6入门》中对ES6 Set的介绍。</p>
<p><a href="http://es6.ruanyifeng.com/#docs/set-map#WeakSet" target="_blank" rel="noopener">《ECMAScript 6入门》– Set和Map数据结构</a></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/学习JavaScript数据结构与算法（二）：链表/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/学习JavaScript数据结构与算法（二）：链表/" itemprop="url">学习JavaScript数据结构与算法（二）：链表</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T17:38:52+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/javascript/" itemprop="url" rel="index">
                    <span itemprop="name">javascript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <blockquote>
<p><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%80%EF%BC%89%EF%BC%9A%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/">学习JavaScript数据结构与算法（一）：栈与队列</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%BA%8C%EF%BC%89%EF%BC%9A%E9%93%BE%E8%A1%A8/">学习JavaScript数据结构与算法（二）：链表</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%89%EF%BC%89%EF%BC%9A%E9%9B%86%E5%90%88/">学习JavaScript数据结构与算法（三）：集合</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E5%9B%9B%EF%BC%89%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/">学习JavaScript数据结构与算法（四）：二叉搜索树</a></p>
</blockquote>
<h1 id="链表简介"><a href="#链表简介" class="headerlink" title="链表简介"></a>链表简介</h1><p>链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。(有C语言基础的可能比较好理解)。<br>使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度)，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。</p>
<p>接下来就是介绍两种常见的链表: 单向链表，双向链表在JavaScript中的实现。</p>
<h1 id="单向链表"><a href="#单向链表" class="headerlink" title="单向链表"></a>单向链表</h1><p>链表中最简单的形式就是单向链表，链表中的节点都包含两个部分，第一部分储存着自身信息，第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL，如图所示:<br><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（二）：链表/link1.png" alt="单向链表图示2"></p>
<h2 id="JavaScipt中单向链表的实现"><a href="#JavaScipt中单向链表的实现" class="headerlink" title="JavaScipt中单向链表的实现"></a>JavaScipt中单向链表的实现</h2><p>首先，创建一个构造函数。<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 单向链表构造函数</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">LinkedList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="comment">/**</span></span><br><span class="line"><span class="comment">   * 单向链表中节点的构造函数</span></span><br><span class="line"><span class="comment">   * @param &#123;Any&#125; element 要传入链表的节点</span></span><br><span class="line"><span class="comment">   */</span></span><br><span class="line">  <span class="keyword">var</span> Node = <span class="function"><span class="keyword">function</span><span class="params">(element)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.element = element;</span><br><span class="line">    <span class="comment">//下个节点的地址</span></span><br><span class="line">    <span class="keyword">this</span>.next = <span class="literal">null</span>;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="comment">//单向链表的长度</span></span><br><span class="line">  <span class="keyword">var</span> length = <span class="number">0</span>;</span><br><span class="line">  <span class="comment">//单向链表的头结点，初始化为NULL</span></span><br><span class="line">  <span class="keyword">var</span> head = <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>不难看出，单向链表构造函数比栈与队列要复杂许多。</p>
<p>单向链表需要有如下的方法:</p>
<ul>
<li><p>append(element): 添加元素到链表尾部</p>
</li>
<li><p>insert(position,element): 向单向链表中某个位置插入元素</p>
</li>
<li><p>indexOf(element): 寻找某个元素在单向链表中的位置</p>
</li>
<li><p>remove(element): 移除给定的元素</p>
</li>
<li><p>removeAt(position): 移除单向链表中某个位置的元素</p>
</li>
<li><p>getHead(): 获取单向链表的头部</p>
</li>
<li><p>isAmpty(): 检查单向链表是否为空，为空则返回true</p>
</li>
<li><p>toString(): 将链表所有内容以字符串输出</p>
</li>
<li><p>size(): 返回单向链表长度</p>
</li>
</ul>
<h3 id="append方法"><a href="#append方法" class="headerlink" title="append方法:"></a>append方法:</h3><p>说明: 向单向链表尾部添加元素。<br>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 向单向链表尾部添加元素</span><br><span class="line"> * @param  &#123;Any&#125; element 要加入链表的节点</span><br><span class="line"> */</span><br><span class="line">this.append = function(element) &#123;</span><br><span class="line">  var <span class="keyword">node</span> <span class="title">= new</span> <span class="keyword">Node</span><span class="title">(element</span>);</span><br><span class="line">  var current;</span><br><span class="line"></span><br><span class="line">  if (head == null) &#123;</span><br><span class="line">    head = <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">  &#125; else</span> &#123;</span><br><span class="line">    // 当前项等于链表头部元素.</span><br><span class="line">    // while循环到最后一个，从而将该节点加入链表尾部。</span><br><span class="line">    current = head;</span><br><span class="line">    // 当next为null时，判定为<span class="literal">false</span>。退出循环。</span><br><span class="line">    while (current.next) &#123;</span><br><span class="line">      current = current.next;</span><br><span class="line">    &#125;</span><br><span class="line">    current.next = <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">  &#125;</span></span><br><span class="line"><span class="title">  length</span>++;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="insert方法"><a href="#insert方法" class="headerlink" title="insert方法:"></a>insert方法:</h3><p>说明: 向单向链表中某个位置插入元素。<br>实现:<br><figure class="highlight xquery"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 向单向链表中插入某个元素</span><br><span class="line"> * @param  &#123;Number&#125;<span class="built_in"> position</span> 要插入的位置</span><br><span class="line"> * @param  &#123;Any&#125; <span class="keyword">element</span>  要插入的元素</span><br><span class="line"> * @return &#123;Boolean&#125;          插入成功返<span class="built_in">回true</span>，失败返<span class="built_in">回false</span></span><br><span class="line"> */</span><br><span class="line">this.<span class="keyword">insert</span> = <span class="keyword">function</span><span class="built_in">(position</span>, <span class="keyword">element</span>) &#123;</span><br><span class="line">  <span class="keyword">if</span> <span class="built_in">(position</span> &gt;= <span class="number">0</span> &amp;&amp;<span class="built_in"> position</span> &lt;= length) &#123;</span><br><span class="line">    var <span class="type">node</span> = new Node(<span class="keyword">element</span>);</span><br><span class="line">    var current = head;</span><br><span class="line">    var previous;</span><br><span class="line">    var index = 0;</span><br><span class="line"></span><br><span class="line">    if (position == 0) &#123;</span><br><span class="line">      <span class="type">node</span>.<span class="keyword">next</span> = current;</span><br><span class="line">     <span class="built_in"> head</span> = <span class="type">node</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      while (index++ &lt;<span class="built_in"> position</span>) &#123;</span><br><span class="line">        <span class="keyword">previous</span> = current;</span><br><span class="line">        current = current.<span class="keyword">next</span>;</span><br><span class="line">      &#125;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">previous</span>.<span class="keyword">next</span> = <span class="type">node</span>;</span><br><span class="line">      <span class="type">node</span>.<span class="keyword">next</span> = current;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    length++;</span><br><span class="line">    <span class="keyword">return</span><span class="built_in"> true</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="keyword">return</span><span class="built_in"> false</span>;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="indexOf方法"><a href="#indexOf方法" class="headerlink" title="indexOf方法:"></a>indexOf方法:</h3><p>说明：寻找某个元素在单向链表中的位置。<br>实现:<br><figure class="highlight xquery"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 寻找某个元素在单向链表中的位置</span><br><span class="line"> * @param  &#123;Any&#125; <span class="keyword">element</span> 要寻找的元素</span><br><span class="line"> * @return &#123;Number&#125;         返回值&gt;=<span class="number">0</span>则代表找到相应位置</span><br><span class="line"> */</span><br><span class="line">this.indexOf = <span class="keyword">function</span>(<span class="keyword">element</span>) &#123;</span><br><span class="line">  var current =<span class="built_in"> head</span>;</span><br><span class="line">  var index = -<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">  while (current) &#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="keyword">element</span> === current.<span class="keyword">element</span>) &#123;</span><br><span class="line">      <span class="keyword">return</span> index;</span><br><span class="line">    &#125;</span><br><span class="line">    index++;</span><br><span class="line">    current = current.<span class="keyword">next</span>;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="remove方法"><a href="#remove方法" class="headerlink" title="remove方法:"></a>remove方法:</h3><p>说明: 移除给定的元素。<br>实现:<br><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 移除给定的元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  &#123;Any&#125; element 要移除的元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> &#123;Number&#125;         返回值&gt;=0表示移除成功</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.remove = function(element) &#123;</span><br><span class="line">  <span class="keyword">var</span> index = <span class="keyword">this</span>.indexOf(element);</span><br><span class="line">  <span class="keyword">return</span> <span class="keyword">this</span>.removeAt(index);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="removeAt方法"><a href="#removeAt方法" class="headerlink" title="removeAt方法:"></a>removeAt方法:</h3><p>说明:移除单向链表中某个位置的元素。<br>实现:<br><figure class="highlight xquery"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 移除单向链表中某一个元素</span><br><span class="line"> * @param  &#123;Number&#125;<span class="built_in"> position</span> 要移除元素的位置</span><br><span class="line"> * @<span class="keyword">return</span> &#123;Any&#125;          移除成功返回被移除的元素，不成功则返回NULL</span><br><span class="line"> */</span><br><span class="line">this.removeAt = <span class="keyword">function</span><span class="built_in">(position</span>) &#123;</span><br><span class="line">  <span class="keyword">if</span> <span class="built_in">(position</span> &gt; -<span class="number">1</span> &amp;&amp;<span class="built_in"> position</span> &lt; length) &#123;</span><br><span class="line">    var current =<span class="built_in"> head</span>;</span><br><span class="line">    var <span class="keyword">previous</span>;</span><br><span class="line">    var index = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">(position</span> == <span class="number">0</span>) &#123;</span><br><span class="line">      // 因为之<span class="built_in">前head</span>指向第一个元素，现在<span class="built_in">把head</span>修改为指向第二个元素。</span><br><span class="line">      // 核心概念在于链表前后全靠指针链接，而非数组一般。</span><br><span class="line">      // 所以只需要改<span class="built_in">变head</span>的元素。</span><br><span class="line">     <span class="built_in"> head</span> = current.<span class="keyword">next</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      while (index++ &lt;<span class="built_in"> position</span>) &#123;</span><br><span class="line">        // <span class="keyword">previous</span>指要操作元素位置之前的那个元素，current表示之后的那个元素。</span><br><span class="line">        <span class="keyword">previous</span> = current;</span><br><span class="line">        current = current.<span class="keyword">next</span>;</span><br><span class="line">      &#125;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">previous</span>.<span class="keyword">next</span> = current.<span class="keyword">next</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    length--;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> current.<span class="type">element</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> null;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="getHead方法"><a href="#getHead方法" class="headerlink" title="getHead方法:"></a>getHead方法:</h3><p>说明:获取单向链表的头部。<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 获取单向链表的头部</span></span><br><span class="line"><span class="comment"> * @return &#123;Any&#125; 单向链表的头部</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.getHead = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="isAmpty、toString、size方法"><a href="#isAmpty、toString、size方法" class="headerlink" title="isAmpty、toString、size方法"></a>isAmpty、toString、size方法</h3><p>实现:<br><figure class="highlight qml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 判断单向链表是否为空</span></span><br><span class="line"><span class="comment"> * @return &#123;Boolean&#125; 为空则返回true，不为空则返回false</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.isAmpty = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> length === <span class="number">0</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将链表所有内容以字符串输出</span></span><br><span class="line"><span class="comment"> * @return &#123;String&#125; 要输出的字符串</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.toString = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">var</span> current = head;</span><br><span class="line">  <span class="keyword">var</span> <span class="built_in">string</span> = <span class="string">''</span>;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">while</span> (current) &#123;</span><br><span class="line">    <span class="built_in">string</span> += current.element;</span><br><span class="line">    current = current.next;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> <span class="built_in">string</span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回单向链表长度</span></span><br><span class="line"><span class="comment"> * @return &#123;Number&#125; 单向链表的长度</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.size = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> length;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h1 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h1><p>双向链表与单向链表很是相像。在单向链表中，只有指向下一个节点的链接。但在双向链表中，还有指向上一个节点的链接，是双向的。<br>如图所示:<br><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（二）：链表/dlink.png" alt="双向链表图示"></p>
<h2 id="JavaScipt中双向链表的实现"><a href="#JavaScipt中双向链表的实现" class="headerlink" title="JavaScipt中双向链表的实现"></a>JavaScipt中双向链表的实现</h2><p>首先，依然是构造函数:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 双向链表的构造函数</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">DoublyLinkedList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="comment">/**</span></span><br><span class="line"><span class="comment">   * 双向链表中节点的构造函数</span></span><br><span class="line"><span class="comment">   * @param &#123;Any&#125; element 要传入链表的元素</span></span><br><span class="line"><span class="comment">   */</span></span><br><span class="line">  <span class="keyword">var</span> Node = <span class="function"><span class="keyword">function</span><span class="params">(element)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">this</span>.element = element;</span><br><span class="line">    <span class="keyword">this</span>.prev = <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">this</span>.next = <span class="literal">null</span>;</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="comment">//双向链表的长度</span></span><br><span class="line">  <span class="keyword">var</span> length = <span class="number">0</span>;</span><br><span class="line">  <span class="comment">//双向链表的头结点，初始化为NULL</span></span><br><span class="line">  <span class="keyword">var</span> head = <span class="literal">null</span>;</span><br><span class="line">  <span class="comment">//双向链表的尾结点，初始化为NULL</span></span><br><span class="line">  <span class="keyword">var</span> tail = <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>双向链表需要有如下的方法:</p>
<ul>
<li><p>append(element): 添加元素到双向链表尾部</p>
</li>
<li><p>insert(position,element): 向双向链表中某个位置插入元素</p>
</li>
<li><p>removeAt(position): 移除双向链表中某个位置的元素</p>
</li>
<li><p>showHead(): 获取双向链表的头部</p>
</li>
<li><p>showLength(): 获取双向链表长度</p>
</li>
<li><p>showTail(): 获取双向链表尾部</p>
</li>
</ul>
<h3 id="append方法-1"><a href="#append方法-1" class="headerlink" title="append方法:"></a>append方法:</h3><p>说明: 添加元素到双向链表尾部<br>实现:<br><figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 向链表尾部添加元素</span><br><span class="line"> * @param  &#123;Any&#125; element 要加入链表的节点</span><br><span class="line"> * @return &#123;Any&#125;         加入链表的节点</span><br><span class="line"> */</span><br><span class="line">this.append = function(element) &#123;</span><br><span class="line">  var <span class="keyword">node</span> <span class="title">= new</span> <span class="keyword">Node</span><span class="title">(element</span>);</span><br><span class="line"></span><br><span class="line">  if (head === null) &#123;</span><br><span class="line">    head = <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">    tail</span> = <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">  &#125; else</span> &#123;</span><br><span class="line">    var previous;</span><br><span class="line">    var current = head;</span><br><span class="line"></span><br><span class="line">    while (current.next) &#123;</span><br><span class="line">      current = current.next;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    current.next = <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">    node</span>.prev = current;</span><br><span class="line">    tail = <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">  &#125;</span></span><br><span class="line"><span class="title"></span></span><br><span class="line"><span class="title">  length</span>++;</span><br><span class="line">  return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">&#125;;</span></span><br></pre></td></tr></table></figure></p>
<h3 id="insert方法-1"><a href="#insert方法-1" class="headerlink" title="insert方法:"></a>insert方法:</h3><p>说明: 向双向链表中某个位置插入元素。<br>实现:<br><figure class="highlight xquery"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 向链表中插入某个元素</span><br><span class="line"> * @param  &#123;Number&#125;<span class="built_in"> position</span> 要插入的位置</span><br><span class="line"> * @<span class="keyword">return</span> &#123;Boolean&#125;         插入成功返<span class="built_in">回true</span>，失败返<span class="built_in">回false</span></span><br><span class="line"> */</span><br><span class="line">this.<span class="keyword">insert</span> = <span class="keyword">function</span><span class="built_in">(position</span>, <span class="keyword">element</span>) &#123;</span><br><span class="line">  <span class="keyword">if</span> <span class="built_in">(position</span> &gt;= <span class="number">0</span> &amp;&amp;<span class="built_in"> position</span> &lt;= length) &#123;</span><br><span class="line"></span><br><span class="line">    var <span class="type">node</span> = new Node(<span class="keyword">element</span>);</span><br><span class="line">    var index = 0;</span><br><span class="line">    var previous;</span><br><span class="line">    var current = head;</span><br><span class="line"></span><br><span class="line">    if (position === 0) &#123;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">if</span> <span class="built_in">(head</span> === null) &#123;</span><br><span class="line">       <span class="built_in"> head</span> = <span class="type">node</span>;</span><br><span class="line">       <span class="built_in"> tail</span> = <span class="type">node</span>;</span><br><span class="line">      &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        current.prev = <span class="type">node</span>;</span><br><span class="line">        <span class="type">node</span>.<span class="keyword">next</span> = current;</span><br><span class="line">       <span class="built_in"> head</span> = <span class="type">node</span>;</span><br><span class="line">      &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> <span class="built_in">(position</span> === length) &#123;</span><br><span class="line"></span><br><span class="line">      current =<span class="built_in"> tail</span>;</span><br><span class="line">      current.<span class="keyword">next</span> = <span class="type">node</span>;</span><br><span class="line">      <span class="type">node</span>.prev = current;</span><br><span class="line">     <span class="built_in"> tail</span> = <span class="type">node</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line"></span><br><span class="line">      while (index++ &lt;<span class="built_in"> position</span>) &#123;</span><br><span class="line">        <span class="keyword">previous</span> = current;</span><br><span class="line">        current = current.<span class="keyword">next</span>;</span><br><span class="line">      &#125;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">previous</span>.<span class="keyword">next</span> = <span class="type">node</span>;</span><br><span class="line">      <span class="type">node</span>.prev = <span class="keyword">previous</span>;</span><br><span class="line">      current.prev = <span class="type">node</span>;</span><br><span class="line">      <span class="type">node</span>.<span class="keyword">next</span> = current;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    length++;</span><br><span class="line">    <span class="keyword">return</span><span class="built_in"> true</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="keyword">return</span><span class="built_in"> false</span>;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="removeAt方法-1"><a href="#removeAt方法-1" class="headerlink" title="removeAt方法:"></a>removeAt方法:</h3><p>说明:移除双向链表中某个位置的元素。<br>实现:<br><figure class="highlight xquery"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> * 移除链表中某一个元素</span><br><span class="line"> * @param  &#123;Number&#125;<span class="built_in"> position</span> 要移除元素的位置</span><br><span class="line"> * @<span class="keyword">return</span> &#123;Any&#125;             移除成功返回被移除的元素，不成功则返<span class="built_in">回false</span></span><br><span class="line"> */</span><br><span class="line">this.removeAt = <span class="keyword">function</span><span class="built_in">(position</span>) &#123;</span><br><span class="line">  <span class="keyword">if</span> <span class="built_in">(position</span> &gt; -<span class="number">1</span> &amp;&amp;<span class="built_in"> position</span> &lt; length) &#123;</span><br><span class="line">    var current =<span class="built_in"> head</span>;</span><br><span class="line">    var index = <span class="number">0</span>;</span><br><span class="line">    var <span class="keyword">previous</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">(position</span> === <span class="number">0</span>) &#123;</span><br><span class="line">     <span class="built_in"> head</span> = current.<span class="keyword">next</span>;</span><br><span class="line"></span><br><span class="line">      <span class="keyword">if</span> (length === <span class="number">1</span>) &#123;</span><br><span class="line">       <span class="built_in"> tail</span> = null;</span><br><span class="line">       <span class="built_in"> head</span>.prev = null;</span><br><span class="line">      &#125;</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> <span class="built_in">(position</span> === length - <span class="number">1</span>) &#123;</span><br><span class="line">      current =<span class="built_in"> tail</span>;</span><br><span class="line">     <span class="built_in"> tail</span> = current.prev;</span><br><span class="line">     <span class="built_in"> tail</span>.<span class="keyword">next</span> = null;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      while (index++ &lt;<span class="built_in"> position</span>) &#123;</span><br><span class="line">        <span class="keyword">previous</span> = current.prev;</span><br><span class="line">        current = current.<span class="keyword">next</span>;</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="keyword">previous</span>.<span class="keyword">next</span> = current.<span class="keyword">next</span>;</span><br><span class="line">      current.<span class="keyword">next</span>.prev = <span class="keyword">previous</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    length--;</span><br><span class="line">    <span class="keyword">return</span> current.<span class="type">element</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="keyword">return</span><span class="built_in"> false</span>;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="showHead、showLength、showTail方法"><a href="#showHead、showLength、showTail方法" class="headerlink" title="showHead、showLength、showTail方法"></a>showHead、showLength、showTail方法</h3><p>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 获取链表的头部</span></span><br><span class="line"><span class="comment"> * @return &#123;Any&#125; 链表的头部</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.showHead = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> head;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 获取链表长度</span></span><br><span class="line"><span class="comment"> * @return &#123;Number&#125; 链表长度</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.showLength = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> length;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 获取链表尾部</span></span><br><span class="line"><span class="comment"> * @return &#123;Any&#125; 链表尾部</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.showTail = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> tail;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<p>感想<br>链表这一节，基本全部都是先按需求写代码，写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑，逻辑也很混乱。看来还是太年轻了。</p>
<p>有兴趣的同学，也可以自己试试只看要求先写代码，写完后再与书上比对，就知道自己的不足了。</p>
<p>前端路漫漫，且行且歌~</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/javascript之数组操作/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/javascript之数组操作/" itemprop="url">javascript之数组操作</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T17:16:56+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/javascript/" itemprop="url" rel="index">
                    <span itemprop="name">javascript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h1 id="一、数组的操作方法"><a href="#一、数组的操作方法" class="headerlink" title="一、数组的操作方法"></a>一、数组的操作方法</h1><h2 id="1、数组的创建"><a href="#1、数组的创建" class="headerlink" title="1、数组的创建"></a>1、数组的创建</h2><p><code>var arrayObj = new Array();　//创建一个数组</code></p>
<p><code>var arrayObj = new Array([size]);　//创建一个数组并指定长度，注意不是上限，是长度</code></p>
<p><code>var arrayObj = new Array([element0[, element1[, ...[, elementN]]]]);　创建一个数组并赋值</code></p>
<p>要说明的是，虽然第二种方法创建数组指定了长度，但实际上所有情况下数组都是变长的，也就是说即使指定了长度为5，仍然可以将元素存储在规定长度以外的，注意：这时长度会随之改变。</p>
<h2 id="2、数组的元素的访问"><a href="#2、数组的元素的访问" class="headerlink" title="2、数组的元素的访问"></a>2、数组的元素的访问</h2><p><code>var testGetArrValue=arrayObj[1]; //获取数组的元素值</code></p>
<p><code>arrayObj[1]= &quot;这是新值&quot;; //给数组元素赋予新的值</code></p>
<h2 id="3、数组元素的添加"><a href="#3、数组元素的添加" class="headerlink" title="3、数组元素的添加"></a>3、数组元素的添加</h2><p><code>arrayObj. push([item1 [item2 [. . . [itemN ]]]]);// 将一个或多个新元素添加到数组结尾，并返回数组新长度</code></p>
<p><code>arrayObj.unshift([item1 [item2 [. . . [itemN ]]]]);// 将一个或多个新元素添加到数组开始，数组中的元素自动后移，返回数组新长度</code></p>
<p><code>arrayObj.splice(insertPos,0,[item1[, item2[, . . . [,itemN]]]]);//将一个或多个新元素插入到数组的指定位置，插入位置的元素自动后移，返回&quot;&quot;。</code></p>
<h2 id="4、数组元素的删除"><a href="#4、数组元素的删除" class="headerlink" title="4、数组元素的删除"></a>4、数组元素的删除</h2><p><code>arrayObj.pop(); //移除最后一个元素并返回该元素值</code></p>
<p><code>arrayObj.shift(); //移除最前一个元素并返回该元素值，数组中元素自动前移</code></p>
<p><code>arrayObj.splice(deletePos,deleteCount); //删除从指定位置deletePos开始的指定数量deleteCount的元素，数组形式返回所移除的元素</code></p>
<h2 id="5、数组的截取和合并"><a href="#5、数组的截取和合并" class="headerlink" title="5、数组的截取和合并"></a>5、数组的截取和合并</h2><p><code>arrayObj.slice(start, [end]); //以数组的形式返回数组的一部分，注意不包括 end 对应的元素，如果省略 end 将复制 start 之后的所有元素</code></p>
<p><code>arrayObj.concat([item1[, item2[, . . . [,itemN]]]]); //将多个数组（也可以是字符串，或者是数组和字符串的混合）连接为一个数组，返回连接好的新的数组</code></p>
<h2 id="6、数组的拷贝"><a href="#6、数组的拷贝" class="headerlink" title="6、数组的拷贝"></a>6、数组的拷贝</h2><p><code>arrayObj.slice(0); //返回数组的拷贝数组，注意是一个新的数组，不是指向</code></p>
<p><code>arrayObj.concat(); //返回数组的拷贝数组，注意是一个新的数组，不是指向</code></p>
<h2 id="7、数组元素的排序"><a href="#7、数组元素的排序" class="headerlink" title="7、数组元素的排序"></a>7、数组元素的排序</h2><p><code>arrayObj.reverse(); //反转元素（最前的排到最后、最后的排到最前），返回数组地址</code></p>
<p><code>arrayObj.sort(); //对数组元素排序，返回数组地址</code></p>
<h2 id="8、数组元素的字符串化"><a href="#8、数组元素的字符串化" class="headerlink" title="8、数组元素的字符串化"></a>8、数组元素的字符串化</h2><p><code>arrayObj.join(separator); //返回字符串，这个字符串将数组的每一个元素值连接在一起，中间用 separator 隔开。</code></p>
<p>toLocaleString 、toString 、valueOf：可以看作是join的特殊用法，不常用</p>
<h1 id="二、数组对象的3个属性"><a href="#二、数组对象的3个属性" class="headerlink" title="二、数组对象的3个属性"></a>二、数组对象的3个属性</h1><h2 id="1、length-属性"><a href="#1、length-属性" class="headerlink" title="1、length 属性"></a>1、length 属性</h2><p>Length属性表示数组的长度，即其中元素的个数。因为数组的索引总是由0开始，所以一个数组的上下限分别是：0和length-1。和其他大多数语言不同的是，JavaScript数组的length属性是可变的，这一点需要特别注意。当length属性被设置得更大时，整个数组的状态事实上不会发生变化，仅仅是length属性变大；当length属性被设置得比原来小时，则原先数组中索引大于或等于length的元素的值全部被丢失。下面是演示改变length属性的例子：<br><figure class="highlight lsl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">var arr=[<span class="number">12</span>,<span class="number">23</span>,<span class="number">5</span>,<span class="number">3</span>,<span class="number">25</span>,<span class="number">98</span>,<span class="number">76</span>,<span class="number">54</span>,<span class="number">56</span>,<span class="number">76</span>];</span><br><span class="line"></span><br><span class="line"><span class="comment">//定义了一个包含10个数字的数组</span></span><br><span class="line"></span><br><span class="line">alert(arr.length); <span class="comment">//显示数组的长度10</span></span><br><span class="line"></span><br><span class="line">arr.length=<span class="number">12</span>; <span class="comment">//增大数组的长度</span></span><br><span class="line"></span><br><span class="line">alert(arr.length); <span class="comment">//显示数组的长度已经变为12</span></span><br><span class="line"></span><br><span class="line">alert(arr[<span class="number">8</span>]); <span class="comment">//显示第9个元素的值，为56</span></span><br><span class="line"></span><br><span class="line">arr.length=<span class="number">5</span>; <span class="comment">//将数组的长度减少到5，索引等于或超过5的元素被丢弃</span></span><br><span class="line"></span><br><span class="line">alert(arr[<span class="number">8</span>]); <span class="comment">//显示第9个元素已经变为"undefined"</span></span><br><span class="line"></span><br><span class="line">arr.length=<span class="number">10</span>; <span class="comment">//将数组长度恢复为10</span></span><br><span class="line"></span><br><span class="line">alert(arr[<span class="number">8</span>]); <span class="comment">//虽然长度被恢复为10，但第9个元素却无法收回，显示"undefined"</span></span><br></pre></td></tr></table></figure></p>
<p>由上面的代码我们可以清楚的看到length属性的性质。但length对象不仅可以显式的设置，它也有可能被隐式修改。JavaScript中可以使用一个未声明过的变量，同样，也可以使用一个未定义的数组元素（指索引超过或等于length的元素），这时，length属性的值将被设置为所使用元素索引的值加1。例如下面的代码：<br><figure class="highlight lsl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">var arr=[<span class="number">12</span>,<span class="number">23</span>,<span class="number">5</span>,<span class="number">3</span>,<span class="number">25</span>,<span class="number">98</span>,<span class="number">76</span>,<span class="number">54</span>,<span class="number">56</span>,<span class="number">76</span>];</span><br><span class="line"></span><br><span class="line">alert(arr.length);</span><br><span class="line"></span><br><span class="line">arr[<span class="number">15</span>]=<span class="number">34</span>;</span><br><span class="line"></span><br><span class="line">alert(arr.length);</span><br></pre></td></tr></table></figure></p>
<p>代码中同样是先定义了一个包含10个数字的数组，通过alert语句可以看出其长度为10。随后使用了索引为15的元素，将其赋值为15，即arr[15]=34，这时再用alert语句输出数组的长度，得到的是16。无论如何，对于习惯于强类型编程的开发人员来说，这是一个很令人惊讶的特性。事实上，使用new Array()形式创建的数组，其初始长度就是为0，正是对其中未定义元素的操作，才使数组的长度发生变化。</p>
<p>由上面的介绍可以看到，length属性是如此的神奇，利用它可以方便的增加或者减少数组的容量。因此对length属性的深入了解，有助于在开发过程中灵活运用。</p>
<h2 id="2、prototype-属性"><a href="#2、prototype-属性" class="headerlink" title="2、prototype 属性"></a>2、prototype 属性</h2><p>返回对象类型原型的引用。prototype 属性是 object 共有的。</p>
<p>objectName.prototype</p>
<p>objectName 参数是object对象的名称。</p>
<p>说明：用 prototype 属性提供对象的类的一组基本功能。 对象的新实例“继承”赋予该对象原型的操作。</p>
<p>对于数组对象，以下例子说明prototype 属性的用途。</p>
<p>给数组对象添加返回数组中最大元素值的方法。要完成这一点，声明一个函数，将它加入 Array.prototype， 并使用它。<br><figure class="highlight matlab"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">array_max</span><span class="params">( )</span></span></span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line">   var <span class="built_in">i</span>, <span class="built_in">max</span> = this[<span class="number">0</span>];</span><br><span class="line"></span><br><span class="line">   <span class="keyword">for</span> (<span class="built_in">i</span> = <span class="number">1</span>; <span class="built_in">i</span> &lt; this.<span class="built_in">length</span>; <span class="built_in">i</span>++)</span><br><span class="line"></span><br><span class="line">   &#123;</span><br><span class="line"></span><br><span class="line">   <span class="keyword">if</span> (<span class="built_in">max</span> &lt; this[<span class="built_in">i</span>])</span><br><span class="line"></span><br><span class="line">   <span class="built_in">max</span> = this[<span class="built_in">i</span>];</span><br><span class="line"></span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   <span class="keyword">return</span> <span class="built_in">max</span>;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">Array.prototype.<span class="built_in">max</span> = array_max;</span><br><span class="line"></span><br><span class="line">var x = new Array(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>);</span><br><span class="line"></span><br><span class="line">var y = x.<span class="built_in">max</span>( );</span><br></pre></td></tr></table></figure></p>
<p>该代码执行后，y 保存数组 x 中的最大值，或说 6。</p>
<h2 id="3、constructor-属性"><a href="#3、constructor-属性" class="headerlink" title="3、constructor 属性"></a>3、constructor 属性</h2><p>表示创建对象的函数。</p>
<p><code>object.constructor //object是对象或函数的名称。</code></p>
<p>说明：constructor 属性是所有具有 prototype 的对象的成员。它们包括除 Global 和 Math 对象以外的所有 JScript 固有对象。constructor 属性保存了对构造特定对象实例的函数的引用。</p>
<p>例如：<br><figure class="highlight gauss"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">x = <span class="keyword">new</span> <span class="keyword">String</span>(<span class="string">"Hi"</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> (x.constructor == <span class="keyword">String</span>) <span class="comment">// 进行处理（条件为真）。</span></span><br></pre></td></tr></table></figure></p>
<p>或</p>
<figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">MyFunc</span> </span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 函数体。</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">y = <span class="keyword">new</span> MyFunc;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> (y.constructor == MyFunc) <span class="comment">// 进行处理（条件为真）。</span></span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/学习JavaScript数据结构与算法（一）：栈与队列/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/学习JavaScript数据结构与算法（一）：栈与队列/" itemprop="url">学习JavaScript数据结构与算法（一）：栈与队列</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T16:55:30+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/javascript/" itemprop="url" rel="index">
                    <span itemprop="name">javascript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <blockquote>
<p><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%80%EF%BC%89%EF%BC%9A%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97/">学习JavaScript数据结构与算法（一）：栈与队列</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%BA%8C%EF%BC%89%EF%BC%9A%E9%93%BE%E8%A1%A8/">学习JavaScript数据结构与算法（二）：链表</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E4%B8%89%EF%BC%89%EF%BC%9A%E9%9B%86%E5%90%88/">学习JavaScript数据结构与算法（三）：集合</a><br><a href="https://lhweb.gitee.io/blog/2018/09/23/%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%EF%BC%88%E5%9B%9B%EF%BC%89%EF%BC%9A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/">学习JavaScript数据结构与算法（四）：二叉搜索树</a></p>
</blockquote>
<h1 id="学习起因"><a href="#学习起因" class="headerlink" title="学习起因"></a>学习起因</h1><p>曾经有一次在逛V2EX时，碰到这么一个帖子。</p>
<blockquote>
<p>数学完全还给老师了，想学回一些基础数学，大概是高中程度的，有什么书籍推荐？</p>
</blockquote>
<p>发帖的楼主大学没有高数课程，出去工作时一直在从事前端的工作。感觉到数学知识的匮乏，所以想补一补数学。<br>看了看帖子，感觉和我很像，因为我的专业是不开高数的，我学的也是前端。也同样感觉到了数学知识匮乏所带来的困顿。同时因为自己的数学思维实在是不怎么好，所以决定努力补习数学与计算机基础知识。</p>
<p>当时也有人说:”前端需要什么数据结构与算法”，但是对于这个事情我有自己的看法。</p>
<blockquote>
<p>我并不认为前端不需要算法之类的知识，在我看来前端具备坚实的计算机基础，对自身发展是极其有利的。我想做程序员。而不是一辈子的初级前端和码农。</p>
</blockquote>
<p>也算是给自己的勉励吧。毕竟基础决定上限，再加上自己对计算机真的很感兴趣，所以学起来就算很累，但也是很幸福的。于是去网上选购了《学习JavaScript数据结构与算法》这本书，配合着去图书馆借阅的《大话数据结构》，开始了数据结构与算法的初步学习。</p>
<p><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（一）：栈与队列/ds.png" alt></p>
<p>这本书讲的内容很是不错，清晰易懂。同时用JavaScipt语言实现，学起来的难度低。值得一看呢。</p>
<h1 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h1><p>书中前两章是对JavaScipt基础与数组常用操作的讲解，如果不清楚的话,推荐去看看下面这篇博客。</p>
<p><a href="https://lhweb.gitee.io/blog/2018/09/23/javascript%E4%B9%8B%E6%95%B0%E7%BB%84%E6%93%8D%E4%BD%9C/">JavaScipt之数组操作</a></p>
<p>接下来就是数据结构的第一部分，栈。</p>
<p>栈是一种遵从后进先出原则(LIFO,全称为Last In First Out)的有序集合。栈顶永远是最新的元素。<br>举个例子就是:栈就像放在箱子里的一叠书 你要拿下面的书先要把上面的书拿开。(当然，你不能先拿下面的书。)<br>看图示也可明白。</p>
<p><img src="/blog/2018/09/23/学习JavaScript数据结构与算法（一）：栈与队列/stack.jpg" alt></p>
<h2 id="JavaScipt中栈的实现"><a href="#JavaScipt中栈的实现" class="headerlink" title="JavaScipt中栈的实现"></a>JavaScipt中栈的实现</h2><p>首先，创建一个构造函数。<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 栈的构造函数</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">Stack</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">  <span class="comment">// 用数组来模拟栈</span></span><br><span class="line">  <span class="keyword">var</span> item = [];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>栈需要有如下的方法:</p>
<ul>
<li><p>push(element(s)): 添加几个元素到栈顶</p>
</li>
<li><p>pop(): 移除并返回栈顶元素</p>
</li>
<li><p>peek(): 返回栈顶元素</p>
</li>
<li><p>isAmpty: 检查栈是否为空，为空则返回true</p>
</li>
<li><p>clear: 移除栈中所有元素</p>
</li>
<li><p>size: 返回栈中元素个数。</p>
</li>
<li><p>print: 以字符串显示栈中所有内容</p>
</li>
</ul>
<h3 id="push方法的实现"><a href="#push方法的实现" class="headerlink" title="push方法的实现"></a>push方法的实现</h3><p>说明: 需要往栈中添加新元素，元素位置在队列的末尾。也就是说，我们可以用数组的push方法来模拟实现。<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将元素送入栈，放置于数组的最后一位</span></span><br><span class="line"><span class="comment"> * @param  &#123;Any&#125; element 接受的元素，不限制类型</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.push = <span class="function"><span class="keyword">function</span><span class="params">(element)</span> </span>&#123;</span><br><span class="line">  items.push(element);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="pop方法的实现"><a href="#pop方法的实现" class="headerlink" title="pop方法的实现"></a>pop方法的实现</h3><p>说明: 需要把栈顶元素弹出，同时返回被弹出的值。可以用数组的pop方法来模拟实现。<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 弹出栈顶元素</span></span><br><span class="line"><span class="comment"> * @return &#123;Any&#125; 返回被弹出的值</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.pop = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> items.pop();</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="peek方法的实现"><a href="#peek方法的实现" class="headerlink" title="peek方法的实现"></a>peek方法的实现</h3><p>说明: 查看栈顶元素，可以用数组长度来实现。<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 查看栈顶元素</span></span><br><span class="line"><span class="comment"> * @return &#123;Any&#125; 返回栈顶元素</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.peek = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> items[items.length - <span class="number">1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="其余方法的实现"><a href="#其余方法的实现" class="headerlink" title="其余方法的实现"></a>其余方法的实现</h3><p>说明: 前三个是栈方法的核心，其余方法则在此一次性列出。因为下文要讲的队列，会与这部分有很大重合。<br>实现:<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 确定栈是否为空</span></span><br><span class="line"><span class="comment"> * @return &#123;Boolean&#125; 若栈为空则返回true,不为空则返回false</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.isAmpty = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> items.length === <span class="number">0</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 清空栈中所有内容</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.clear = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  items = [];</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 返回栈的长度</span></span><br><span class="line"><span class="comment"> * @return &#123;Number&#125; 栈的长度</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.size = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> items.length;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 以字符串显示栈中所有内容</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.print = <span class="function"><span class="keyword">function</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">  <span class="built_in">console</span>.log(items.toString());</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h2 id="实际应用"><a href="#实际应用" class="headerlink" title="实际应用"></a>实际应用</h2><p>栈的实际应用比较多，书中有个十进制转二进制的函数。(不懂二进制怎么算的话可以百度)下面是函数的源代码。<br>原理就是输入要转换的数字，不断的除以二并取整。并且最后运用while循环，将栈中所有数字拼接成字符串输出。<br><figure class="highlight maxima"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将10进制数字转为2进制数字</span></span><br><span class="line"><span class="comment"> * @param  &#123;Number&#125; decNumber 要转换的10进制数字</span></span><br><span class="line"><span class="comment"> * @return &#123;Number&#125;           转换后的2进制数字</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">function divideBy2(decNumber) &#123;</span><br><span class="line"></span><br><span class="line">  <span class="built_in">var</span> remStack = <span class="built_in">new</span> Stack(),</span><br><span class="line">    <span class="built_in">rem</span>,</span><br><span class="line">    binaryString = '';</span><br><span class="line"></span><br><span class="line">  <span class="keyword">while</span> (decNumber &gt; <span class="number">0</span>) &#123;</span><br><span class="line">    <span class="built_in">rem</span> = Math.<span class="built_in">floor</span>(decNumber <span class="symbol">%</span> <span class="number">2</span>);</span><br><span class="line">    remStack.<span class="built_in">push</span>(<span class="built_in">rem</span>);</span><br><span class="line">    decNumber = Math.<span class="built_in">floor</span>(decNumber / <span class="number">2</span>);</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">while</span> (!remStack.isAmpty()) &#123;</span><br><span class="line">    binaryString += remStack.<span class="built_in">pop</span>().toString();</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="built_in">return</span> binaryString;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h1 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h1><p>队列与栈是很相像的数据结构，不同之处在于队列是是先进先出(FIFO:First In First Out)的。<br>举个例子: 火车站排队买票，先到的先买。(插队的不算)，是不是很好理解了~</p>
<h2 id="JavaScipt中队列的实现"><a href="#JavaScipt中队列的实现" class="headerlink" title="JavaScipt中队列的实现"></a>JavaScipt中队列的实现</h2><p>队列的实现和栈很像。首先依然是构造函数:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 队列构造函数</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">Queue</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">var</span> items = [];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>队列需要有如下的方法:</p>
<ul>
<li><p>enqueue(element(s)): 向队列尾部添加几个项</p>
</li>
<li><p>dequeue(): 移除队列的第一项(也就是排在最前面的项)</p>
</li>
<li><p>front(): 返回队列的第一个元素，也就是最新添加的那个</p>
</li>
</ul>
<p>其余方法与队列相同</p>
<h3 id="enqueue方法的实现"><a href="#enqueue方法的实现" class="headerlink" title="enqueue方法的实现"></a>enqueue方法的实现</h3><p>说明: 向队列尾部添加几个项。<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将元素推入队列尾部</span></span><br><span class="line"><span class="comment"> * @param  &#123;Any&#125; ele 要推入队列的元素</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.enqueue = <span class="function"><span class="keyword">function</span><span class="params">(ele)</span> </span>&#123;</span><br><span class="line">  items.push(ele);</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="dequeue方法的实现"><a href="#dequeue方法的实现" class="headerlink" title="dequeue方法的实现"></a>dequeue方法的实现</h3><p>说明: 移除队列的第一项。<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将队列中第一个元素弹出</span></span><br><span class="line"><span class="comment"> * @return &#123;Any&#125; 返回被弹出的元素</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.dequeue = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> items.shift()</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="front方法的实现"><a href="#front方法的实现" class="headerlink" title="front方法的实现"></a>front方法的实现</h3><p>说明: 返回队列的第一个元素，也就是最新添加的那个。<br>实现:<br><figure class="highlight actionscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 查看队列的第一个元素</span></span><br><span class="line"><span class="comment"> * @return &#123;Any&#125; 返回队列中第一个元素</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">this</span>.front = <span class="function"><span class="keyword">function</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">return</span> items[<span class="number">0</span>];</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<p>以上的三个方法，就是队列这种数据结构的核心方法了。其实很好理解的。</p>
<h2 id="实际应用-1"><a href="#实际应用-1" class="headerlink" title="实际应用"></a>实际应用</h2><p>书上的是个击鼓传花的小游戏。原理就是循环到相应位置时，队列弹出那个元素。最后留下的就是赢家。<br>源代码如下:<br><figure class="highlight php"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 击鼓传花的小游戏</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  &#123;Array&#125;  nameList 参与人员列表</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  &#123;Number&#125; num      在循环中要被弹出的位置</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> &#123;String&#125;          返回赢家(也就是最后活下来的那个)</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">hotPotato</span><span class="params">(nameList, num)</span> </span>&#123;</span><br><span class="line">  <span class="keyword">var</span> queue = <span class="keyword">new</span> Queue();</span><br><span class="line"></span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; nameList.length; i++) &#123;</span><br><span class="line">    queue.enqueue(nameList[i]);</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">var</span> eliminated = <span class="string">''</span>;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">while</span> (queue.size() &gt; <span class="number">1</span>) &#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; num; i++) &#123;</span><br><span class="line">      queue.enqueue(queue.dequeue());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    eliminated = queue.dequeue();</span><br><span class="line">    console.log(eliminated + <span class="string">" Get out!"</span>)</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  <span class="keyword">return</span> queue.dequeue()</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://lhweb.gitee.io/blog/blog/2018/09/23/TypeScript-不止稳，而且快/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="lhweb">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="编程那点事">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/blog/2018/09/23/TypeScript-不止稳，而且快/" itemprop="url">TypeScript - 不止稳，而且快</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-23T16:22:41+08:00">
                2018-09-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/typescript/" itemprop="url" rel="index">
                    <span itemprop="name">typescript</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h1 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h1><p>关于 TypeScript 是什么，应该大部分人都已经知道了，但是在这儿，还是摘抄一下知乎的回答：</p>
<blockquote>
<p>TypeScript 是 JavaScript 的强类型版本。然后在编译期去掉类型和特有语法，生成纯粹的 JavaScript 代码。由于最终在浏览器中运行的仍然是 JavaScript，所以 TypeScript 并不依赖于浏览器的支持，也并不会带来兼容性问题。</p>
</blockquote>
<p>对于我个人而言， 使用 TypeScript 写项目已经有半年多了，中间有被 TypeScript 的配置与升级折腾到想砸电脑的时候，也有提前发现错误时的暗自庆幸，同时也有因为找不到类型定义文件而自己手写，提PR补全的时候。<br>总的来说使用 TypeScript 的这一年，什么感觉都有。但最后还是依然坚持使用 TypeScript ，因为其带来的效率提升是远远大于环境升级所带来的开销的。</p>
<h1 id="稳定压倒一切"><a href="#稳定压倒一切" class="headerlink" title="稳定压倒一切"></a>稳定压倒一切</h1><p>作为程序员，自然希望代码上线之后能安安稳稳的跑着，而不是突然报错崩溃啥的。<br>所以 TypeScript 之前最被看重的就是静态类型检查功能。</p>
<p>至于静态类型检查的作用，在知乎的另一个回答中有相关的回答：</p>
<blockquote>
<p>静态类型检查可以避免很多不必要的错误, 不用在调试的时候才发现问题 (其实有的时候根本调试不出问题, 只是默默地把坑挖了, 说不定埋的就是个炸弹, 之前用 TypeScript 重写应用的服务器端程序, 写完之后就发现了不少暂时没有影响到运行的严重问题).</p>
</blockquote>
<h1 id="懒人的自我救赎"><a href="#懒人的自我救赎" class="headerlink" title="懒人的自我救赎"></a>懒人的自我救赎</h1><p>然而，我是个很“懒”的人，不愿在重复的事情上花上很多时间，也不喜欢像背书一下，背下来 Api 文档。更希望自己的时间能专注于核心业务的开发，而非边边角角的事情。</p>
<p>去年十月，在因为实际学习需要，接触越来越多前端框架时候，感觉整天的开发，大半的时间都浪费在了查文档上，特别是一些 React 的组件，props又多又长……每次写的时候，都得回去翻文档，简直绝望。<br><img src="/blog/2018/09/23/TypeScript-不止稳，而且快/TB1HHW4SpXXXXbJapXXXXXXXXXX-1878-958.png" alt></p>
<p><img src="/blog/2018/09/23/TypeScript-不止稳，而且快/TB1nPYpSpXXXXcSXFXXXXXXXXXX-269-220.png" alt></p>
<p>在这种每天近乎绝望的重复劳动下，我开始尝试去找解决方法，再到后来有一天接触了 TypeScript ，感觉到这就是自己想要的功能。<br>嗯……看中的不是 TypeScript 的稳定性，而是 TypeScript 的代码提示。</p>
<p>比如写 Node.js，使用 TypeScript 与 不使用的区别是这样的：</p>
<p><img src="/blog/2018/09/23/TypeScript-不止稳，而且快/TB11WrkSpXXXXX_XVXXXXXXXXXX-772-604.png" alt></p>
<p>不仅不用手动翻阅 Api, 而且参数是什么也都一清二楚了。</p>
<p>且TypeScript 的代码提示是基于类型文件工作的，而相比于各个编辑器自己定义的代码片段来说，不仅有大量的志愿者去维护，更新及时，而且种类繁多，基本现有的流行框架类库，都有相应的类型定义文件。</p>
<p>所以自打用上 TypeScript 后，就过上了再也不用去费脑子记 Api 和参数的日子，开发效率与幸福感都得到了大大的提升。</p>
<h1 id="不止稳，更要快"><a href="#不止稳，更要快" class="headerlink" title="不止稳，更要快"></a>不止稳，更要快</h1><p>而 TypeScript 的快，不仅体现在代码提示上，同时也体现于重构、可读性和配套的编辑器上。</p>
<h2 id="代码重构"><a href="#代码重构" class="headerlink" title="代码重构"></a>代码重构</h2><p>在重构上，这个自己是有实际体会的，如果写JS，重构时候不小心改了啥，除了运行时候能发现，其他时候往往难以察觉，且 ESLint 也只能是排查简单的问题，所以出了BUG会非常麻烦。<br>而 TypeScript 不一样，重构了，重新编译一下就知道，哪里错了，哪里改动了不应该改的。对于我自己这种时不时就会重构的人来说，省时又省力。</p>
<h2 id="可读性"><a href="#可读性" class="headerlink" title="可读性"></a>可读性</h2><p>可读性上，TypeScript 明显占优，查看开源代码时，如果注释不是很完善，往往会看的云里雾里，而 TypeScript 在同等条件下，至少有个类型，能让自己更容易明白代码的参数、返回值和意图。</p>
<h2 id="编辑器"><a href="#编辑器" class="headerlink" title="编辑器"></a>编辑器</h2><p>这个是不得不提的部分，因为 VSCode 实在是太方便了，性能也高，且编辑器自身保持着一个高速的开发与迭代状态，时不时就能感受到 VSCode 开发团队的诚意和其所带来的惊喜。</p>
<p>因为都是微软家产品的原因，VSCode 对 TypeScript 的支持也相当完善。各种插件也层出不穷，基于 TypeScript 做的 Automatic Type Acquisition 功能使得 JavaScript 的用户也能享受到详细的代码提示功能，这一点上比 Sublime 等编辑器方便了很多。</p>
<p>关于 VSCode 编辑器的上手与配置，可以看阎王发表的这篇文章：<a href="http://www.barretlee.com/blog/2017/04/21/something-about-vsc/" target="_blank" rel="noopener">如何快速上手一款 IDE - VSC 配置指南和插件推荐</a></p>
<h1 id="解放自己，专注业务核心开发：TypeScript-编辑器插件推荐"><a href="#解放自己，专注业务核心开发：TypeScript-编辑器插件推荐" class="headerlink" title="解放自己，专注业务核心开发：TypeScript 编辑器插件推荐"></a>解放自己，专注业务核心开发：TypeScript 编辑器插件推荐</h1><p>当然，每次写 TypeScript 时，依然会遇到一些烦心的问题和重复的劳动。<br>比如说，TypeScript的类型定义文件是需要手动下载相应的 @types 包的，虽然相比于之前的方式已经进化了很多，但是每次还要重复，依然会觉得繁琐。<br>所以下面会推荐自己常用的几个插件，把自己从繁琐无趣零成长的工作中解放出来。</p>
<h2 id="TypeScript-Importer-告别手动重复写import的日子"><a href="#TypeScript-Importer-告别手动重复写import的日子" class="headerlink" title="TypeScript Importer-告别手动重复写import的日子"></a>TypeScript Importer-告别手动重复写import的日子</h2><p><a href="https://marketplace.visualstudio.com/items?itemName=pmneo.tsimporter" target="_blank" rel="noopener">插件地址：TypeScript Importer</a></p>
<p>这个是我最喜欢的插件，具体的作用，一图胜千言：<br><img src="/blog/2018/09/23/TypeScript-不止稳，而且快/QHByAo9Km7.gif" alt></p>
<p>在长长的路径里，导入另一个文件夹深处的模块，那种感觉是绝望……<br>每次都要重复的import，每次都要重复的判断路径，每次都要重新写一遍import……</p>
<p>虽然工作量也不大，但是确实会影响心情和效率。</p>
<h2 id="Types-auto-installer-自动安装相应的类型定义文件"><a href="#Types-auto-installer-自动安装相应的类型定义文件" class="headerlink" title="Types auto installer - 自动安装相应的类型定义文件"></a>Types auto installer - 自动安装相应的类型定义文件</h2><p><a href="https://marketplace.visualstudio.com/items?itemName=jvitor83.types-autoinstaller" target="_blank" rel="noopener">插件地址：Types auto installer</a></p>
<p>在之前，你安装一个模块并在 TypeScript 运行两段命令。<br>以lodash为例：<br><figure class="highlight stylus"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">npm <span class="selector-tag">i</span> lodash --save</span><br><span class="line">npm <span class="selector-tag">i</span> @types/lodash --save</span><br></pre></td></tr></table></figure></p>
<p>当然，你也可以合并到一句话去写。<br>虽然工作量不大……但是架不住量多啊……每开一个项目都得来这么一次，简直绝望……</p>
<p>所以当时就想着自己写一个自动安装类型定义文件的小工具，后面确实也写出来了，只是再后来又发现 VSCode 有这个插件，功能也很完善，就用它的了。<br>插件的作用很简单，就是当你运行：</p>
<p><code>npm install --save lodash</code><br>它会自动执行：</p>
<p><code>npm install --save @types/lodash</code><br>与此同时还有一键下载安装所有 package.json 依赖类型定义文件的功能，可以说是非常方便了。</p>
<h2 id="Sort-Typescript-Imports-给你import的模块们排序"><a href="#Sort-Typescript-Imports-给你import的模块们排序" class="headerlink" title="Sort Typescript Imports-给你import的模块们排序"></a>Sort Typescript Imports-给你import的模块们排序</h2><p><a href="https://marketplace.visualstudio.com/items?itemName=miclo.sort-typescript-imports" target="_blank" rel="noopener">插件地址：Sort Typescript Imports</a></p>
<p>同样，话不多说，一图胜千言：<br><img src="/blog/2018/09/23/TypeScript-不止稳，而且快/example.gif" alt></p>
<p>这是一个看起来没什么作用的插件……因为其实 import顺序是否整洁有序好像对开发效率啥的并没有很大的提升。<br>但这是一个你接受了它的设定，就可能会觉得十分有趣的插件……</p>
<p>具体的作用就是，让你的 imports 更有顺序，相近文件夹的排列在一起。看起来会更好看一些。</p>
<p>Emmm……如果一定要说作用的话，就是更好看一些吧……很符合我这种有轻微代码洁癖的人的心态……</p>
<h1 id="为什么要关注这个？"><a href="#为什么要关注这个？" class="headerlink" title="为什么要关注这个？"></a>为什么要关注这个？</h1><p>自己在知乎上有回答过一道问题：《最近一年前端技术栈哪些技术点最困扰你?》<br>我的回答是：</p>
<blockquote>
<p>开发环境的搭建。<br>没有官方的cli，或者自己要做一些拓展(比如用ts)真的非常烦人。<br>各种报错，而这种在开发环境上积累的经验和踩的坑是价值非常低的。(因为基本最后翻官方配置文档都能解决)<br>耗时长，学习价值低，更新速度快。</p>
</blockquote>
<p>在这儿，也是同理。<br>用 TypeScript 和相关插件所解决的问题，都是一些繁琐、无趣、零成长的工作，而且还影响心情。<br>有这个时间，为什么不多陪陪女朋友，多学点东西，多解决一些有意思的问题呢？<br>所以这种可以让计算机解决的问题，就让计算机去解决吧~</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/blog/page/2/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/blog/">1</a><a class="page-number" href="/blog/page/2/">2</a><span class="page-number current">3</span><a class="page-number" href="/blog/page/4/">4</a><a class="extend next" rel="next" href="/blog/page/4/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">lhweb</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/blog/archives/">
              
                  <span class="site-state-item-count">39</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/blog/categories/index.html">
                  <span class="site-state-item-count">6</span>
                  <span class="site-state-item-name">categories</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/blog/tags/index.html">
                  <span class="site-state-item-count">25</span>
                  <span class="site-state-item-name">tags</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/blog/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          

          
          

          
          

          

        </div>
      </section>

      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">lhweb</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Muse</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=5.1.4"></script>



  
  

  

  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
